There have been a number of reported Droid GPS failures. Some failures seem to be attributed to former Alltel customers, and some seem to be some sort of software hiccup.
I had my first Droid GPS fail on the second day I had it, and went straight to the nearest VZW store to exchange the phone. I had the second unit for about a week, until that phone's GPS also failed while on a work trip in Gainesville, FL. I then proceeded over the next several hours to try and get the phone's GPS back up.
After a long trial and error process, where I reset the phone about a dozen times, used various orders of operations, etc, I finally got the GPS to get a valid fix, and it has been working great ever since. The symptoms of the GPS failure include a constant "Searching for GPS" message on Maps, and no fix when using the App "GPS Status". In GPS Status, you may have up to 10 satellites in view, but none will lock in a fix. Here is the procedure I went through that got my GPS to lock. Remember, your phone's GPS failure might be related to a different issue, and this might not work. The process only takes about an hour, which is a lot faster than a trip to the VZW store for an exchange.
Warning: this will totally wipe your Droid, but it’s better than a trip to the store and a new phone (which might have another set of issues). Your favorite Apps and Contacts will be re-installed from the Google Sync service, but your home screen will reset to Factory appearance. So, you will have to rebuild your home screen layouts.
1.0: Go to Android Market and select Downloads in the menu button. Go through each non-native, location-based app and uninstall it. This is any app that uses your GPS to get a location. This includes just about any weather or location search app.
1.1: WHY? Your Droid Apps are synced on the Google server. So, following a factory reset, your Droid will re-install any apps you had installed prior to the reset. Uninstalling from the phone only does not remove them from the Google Sync listing.
2.0: Connect your Droid to a PC and mount the SD card. Go to your SD card using the PC and make a copy of the SD card contents to a temp folder for easy access later.
2.1: Unmount the SD card from the PC and go to the Settings > SD Card and Phone Storage menu.
2.2: Select Unmount SD Card
2.3: Select Format SD Card
2.4: Return to Home page and power off phone.
3.0: Remove the Droid back cover and battery. Remove the SD Card and re-install battery.
4.0: Power on Phone normally.4.1: Go to the Settings menu and select Privacy > Factory Data Reset.
4.2: Phone will shutoff, wipe, and power back on. Do not do anything until you get the green Android Graphic on the screen, indicating ready to re-activate phone.
4.3: DO NOT ACTIVATE phone at this time. Instead, power off phone as normal.
4.4: Remove the battery again, and set Droid aside with battery removed for at least 30 minutes.
5.0: After at least 30 minutes, reinstall the battery, but NOT the SD card.5.1: Power up the phone.
5.2: Tap the Android graphic, and the Droid will dial the Verizon system for re-activation. Follow the voice prompts to re-activate the phone. Once activated, the Droid will hang up automatically.
5.3: SKIP the tutorial and sign in to your existing Google Account.
5.4: Allow the phone to sync with Google.
5.5: Go to Settings > Location and Security Settings. Disable Use Wireless Networks.
6.0: Access the Android Market and install the GPS Status application.6.1: Place the Droid in a window with a fairly clear view of the sky.
6.2: Activate the GPS Status application and let phone sit in window for about 15-30 minutes.
6.3: After 30 minutes or so, the GPS fix should be valid and active.
7.0: Using the Advanced Task Killer, kill all apps.7.1: While still in view of the sky, activate the Maps application. Your Location should fix within 10-15 seconds.
7.2: Using Advanced Task Killer, kill all apps, including Maps.
7.3: Go to Settings > Location and Security Settings. Enable Use Wireless Networks.
8.0: Power off phone, remove battery, and re-install SD card.
8.1: Power up Droid normally.
8.2: Connect to PC and Mount SD card.
8.3 Restore SD card contents from Temp folder on PC.
8.4 Power off Droid and power back up.
Procedure Complete. Try the Maps App again to make sure your location fix is still working. Use GPS Status to monitor GPS health.