GPS uses satellites (basic huge clocks in space). It doesn't require an Internet connection itself. You can calculate your coordinates completely offline (but within sight of a couple of satellites).
Offline use has fewer and fewer real uses, and it takes lots of space (although vector maps should be much smaller). They can always cache an area of a few miles surrounding your route, which ought to be fine for wrong-turns (in fact, I'd expect them to do this). They can also cache if you're on roaming but connected to wifi, or use other such heuristics to provide a seamless experience.
Tomtom ought to be worried. As had navigon. This means that basically all smartphones out there now ship with high-quality TBT navigation for free, out-of-the-box. Consumers spoke: they wanted better quality experiences and weren't prepared to pay the exorbitant costs of dinosaur companies trying to protect satnav revenue, thereby forcing new entrants in to the market (in this case, those that had most to gain: the OS vendors themselves). Consumers win.