That "everywhere" means everywhere you can get a connection to at least two, preferably three, GSM towers, right? As long as they have GPS as well, they'll do fine; where cell towers are thin, you're not usually in a steel canyon. (And when you're in a stone canyon, nothing's gonna work well; but as long as you know which one you're in, it doesn't matter so much.) But triangulation (or, pedantically, trilateration) isn't a cure-all by itself.


@Picklesworth
Isn't someone gonna show up and tell us how the Newton did something like that? Really, it had some sorta natural-language parser that would be helpful in this context; your whole plan sounds (from what little I know) like a Newton natural. At least if Jobs hadn't killed the Newtons, so that there'd be GPS Newtons around...