1. You need a line of sight to the satellites from your phone. That means that being in the middle of midtown Manhattan, you're likely to not get a signal. That also means that if you're in the middle of your living room, don't also expect to magically receive a GPS lock. It just doesn't work that way.
2. While it's controversial whether or not bad weather affects GPS signals, I notice that heavy clouds and poor weather affects my phone's ability to lock on at all.
3. If you're in an area where you can't get a lock (i.e. Midtown Manhattan, etc), turn on Google Location Services. This will always put you within a 500-1000 meter radius of where you are (in which case you would just read a map the old fashioned way).
4. I almost never have a problem locking on a location within 5 seconds while driving on a clear day, outside of the city. If your GPS and Google Navigation still does not work in this situation, you probably really have an issue.
5. During my paranoia, I cleared cache/data for Google Framework Services (warning: this will remove your sync account) and uninstalled updates to Maps and reinstalled. That may help if you've been flashing back and forth between roms.
Hope these simple tips might help some people out.