There have been many reports of the iPhone 3G having problems with its GPS positioning. Many users are reporting that they go into Maps on their new iPhone, click the target to lock onto their position and it is just not working. I too was experiencing this and have three things to advise, that may point to a solution.
Firstly, check the version number for your 2.0 software. Mine was factory shipped with 2.0 (5A345). I did a restore through iTunes and it downloaded the later 2.0 (5A347) version. After this was downloaded the iPhone got a cellular signal a lot quicker, plus a lot stronger signal too.
Secondly, check you at least have a cellular or mobile phone network signal. The iPhone (both 3G and first generation) use the cell network to work out your position. I found that once I had a four bar signal or more, the iPhone locked onto my position very quickly. It was not that accurate, but it did respond quickly.
Finally, put your iPhone 3G outside for at least 15 minutes. You will find that if it has a non-restricted path to the satellites you will get it to lock on. After leaving mine outside, the target changed to the blue glowing dot and found my position. It was very very accurate, even tracking if I was at the top or bottom of my back garden. This is very impressive indeed.