I'm sure by now everyone has found a resolution, but I just stared having issues with GPS lock on my Droid X and researched a solution for a few weeks. I cleared the cache, reset my phone, all the basic stuff, but then tried this one trick that I read about a few places. If you press on the area where the red battery tab is (without the battery door works best), it should give your phone the capability to lock on to more than one GPS. From reading, this does one of two things, places pressure on something inside the phone OR prevents the copper tab just below the red tab from touching the metal surface (SMALL shiny metallic area) on the battery door (which may be affecting the antenna).
Anyways, made the fix "semi-permanent" by folding a piece of cellafane tape over and over a few times and placing it under the red tab and then installing the battery door (which will be a little snug).
My Navingation now works perfect and I'm getting 8 GPS showing on my GPS Test app.
Hope this is able to help someone.