I implemented a pretty nice navigation package on Android that uses accelerometers, compass, gyros, and gps. My experience was that while the gyros are good enough to be used to stabilize a game, they drift far too much to be used for navigation.
I wrote a Kalman filter to combine the accelerometer input and gyro input to get a smooth output, but it still needs tuning. However, filter or no filter, I think the gyros will always drift too much to be used for navigation.
The accelerometers are worse, of course. Way too much jitter and noise. Remember that the gps, compass, accelerometers and gyros in a cell phone are designed to be as cheap as possible, not as accurate as possible.