The biggest problem here is that you're confusing GPS (Global Positioning System) with Navigation and Maps.
GPS uses satellites (and nothing else) to provide you with accurate location data, including (at a minimum), Latitude and Longitude.
Most people would not find that raw data useful, so a variety of devices and Apps will plot your location (retrieved using GPS) on a map of some sort.
With iOS, the Maps App uses a data connection - Cellular or Wi-Fi, to download the actual map to display your location on.
When you open the Maps App and there is no data connection, it's complaining because it has no way to load the maps for you. It's not complaining because it can't work out where you are.
Navigon does not do this. It stores the maps on your device, so that when there is no data connection, it can still show you your map and determine your location using GPS.
IN ADDITION to using GPS, iOS can work out your location using less precise methods - specifically using the Wi-Fi networks and cellular base stations within range of your device to establish roughly where you are. These are useful for some Apps (such as a Search Engine) because they don't always need to know exactly where you are. They have three primary benefits:
-they are faster
-they use less power
-they work better indoors
These additional methods of determining your location DO require a data connection.
Navigon is presumably set up so that it will only work if it can get a very precise location from iOS. The less accurate methods (like Wi-Fi) are not suitable for turn by turn navigation.
Based on all of this, I would agree with Applejuiced in agreeing that your device probably has a hardware fault (GPS receiver failure).
