Edit: Noted you had signal, which I suppose answers that question. I'd restore it in DFU mode and see if it comes back. Otherwise, your GPS may be faulty and you need to go to the Apple store.
Edge. I'm on T-Mobile USA so there's no 3G. But... I have a 3GS with the same settings, etc, on T-Mobile USA unlocked and that works fine. The 3G iPhone did work though like a month ago. Since then, it can never determine location.