Follow these exact steps and I would say your problems will most likely be fixed.
Not sure if this first step is necessary, but the program is neat and will tell you where gps satellites are according to your location.
1. Download GPS Status from the market (it's free).
2. Make sure your GPS is turned on.
3. Go to a location where you don't have magnetic devices around you (such as electronics of any sort), such as outside (ideal) or room with minimal electronics nearby.
4. Hold your phone in your hand flat. Spin it around 3 times. After that, hold your phone on it's side, spin it around 3 times again. Finally, put your phone right side up (end on end) and spin it 3 more times. You can also do figure 8's, but the spins worked for me.
5. Go to Google Maps and see if your location is closer.
At first Maps was showing me about half a mile away, I did this trick and it showed the dot on my exact room in my apartment.