I have an LG Ally and everytime I try to go to the nagivation and hit navigate it says searching for GPS signal for like 5 minutes before it loads.
GPS Status is mentioned earlier in this thread but I recommend getting it. It has a GPS reset function that can be handy if the receiver isn't able to obtain a fix. It's also a handy utility app for looking into what's going on with your GPS receiver and getting your particular GPS app out of the equation for testing and troubleshooting.
Next - I have the paid version of GPS Status ... if I have trouble getting my position, I'll let it run a couple minutes - it's far better at finding your position than Google ...
Google Maps uses the very same GPS receiver that GPS Status does. If the GPS receiver isn't able to obtain a fix it isn't a Google Maps issue. Google Maps, however, can use alternate (and less accurate) methods for determining your location if the GPS receiver isn't available for whatever reason.
Next, this works really well, you don't even need GPS Status, just do it in Google maps ... I gone from being a couple miles off to being with in couple feet doing this
If your location is off by more than a few meters you aren't using your GPS receiver. Some have alleged that the steps you mentioned above help but those steps actually calibrate the magnetometer (compass), not the GPS. I suspect that anyone that has seen benefit from this or from simply running GPS Status is assuming that there is some sort of false causal relationship. More than likely, such people just needed to wait for the receiver to obtain a fix.
Again, I'd suggest starting with GPS Status and its reset feature. In every case where my Droid's GPS receiver was not able to get a fix the reset feature has helped.