Do you see the GPS icon blinking? If so then you can try flashing the various GPS fix files, modifying configurations, or waving your phone in the air to recalibrate the sensors. However, after none of those solutions worked for me, I realized the issue was hardware related. The GPS sensor is directly underneath the loudspeaker on the back, behind the plastic cover. Similar to the way the battery cover is the antenna for WiFi/mobile network etc, the upper cover is the antenna for GPS. I found that fiddling around with it, or applying pressure where the speaker is can help achieve a better GPS signal, but if you stop applying pressure, it tends to stop working again.
Download the "GPS Test" app from the market, run it, look at the strength of the GPS and then check again after applying pressure. If you notice the bars go up, then you've found your issue. If you are adventurous enough, you can use a pin to pry open the cover (be careful not to scratch) and you'll see two small metallic connectors below the speaker. You could try to adjust them to provide better contact with the antenna in the plastic cover. That's how I fixed my GPS issues.