I too have seen many troubles with my GPS and the US Cellular network. I use an application called Accutracking that works flawlessly. I also use Cacheberry and it can sort the database from my GPS location, with absolutely no trouble. I used the maps in Yahoo Go without any trouble at all. (Why they work I don't know.) However, Google Maps and Geocache Navigator would work about once out of about 20 tries, and only for a short period of time.
I got so sick of working with it and trying to figure it out, I just went and bought a Bluetooth GPS puck. I don't like having to carry it in my pocket, but what the heck, it makes everything work.
If I had to guess, I would say that US Cellular turned off the GPS (or whatever they turned off) in mid-January of this year. Because, Geocache Navigator worked 100% in early Jan., but around the middle of the month, it quit working correctly. Again, why Yahoo Go, Accutracking and Cacheberry still work fine with the internal gps, I have no idea.