Try the GPS outside or by a window. Unlike cell service which connects to ground towers, satellites that track you are in the air, so a clear view is pretty much the best way to pin point you.
If that doesn't do anything, try a restore in iTunes.
If that doesn't do anything, you probably have a dud iPhone, and need to schedule an appointment at the Genius Bar.