I'm pretty sure GPS does not work if Airplane mode is ON. I could be wrong, of course, but I don't think it works. What some applications do, is simply show your last known location, but it doesn't really update. Google maps does that.
You can use GPS without both Wi-Fi and cellular connection, it just takes longer to make a connection. The people at the apple store probably deactivated airplane mode? That might have been it. Why would you want to keep airplane off anyways?
Even if the GPS connection works with airplane ON, it would take several minutes to establish a connection. For example, if you device only sees one sattelite, it would take it 40 minutes to download a complete almanaq. of course, you'd need at least 4 (3 if they have made a simple improvement) sattelites to get a signal. Since sattelites share the almanaques at different times, that time is cut short. When you have a Wi-Fi/GSM connection, your device 'immediately' gets all the needed information, that's why it's faster.
So, are you really sure your GPS was working in the states with Airplane ON? Or was it just showing a cached location?
Also, are you sure your device was not connected to he store's Wi-Fi connection? That would considerably speed up the GPS acquiring signal.
Another note, most GPS devices (I'm assuming the iPhone does that) store the latest information, so that the next time you reconnect, getting that signal will be much faster (as long as there's not a long period since you last used it).
Assuming you used the iPhone back in the states, you'd have been covered by different sattelites in each of the visited countries, so you'd really need to wait for the full information. For the first time at least.
Anyways, no Wi-Fi or cellular connection, means you'll have to wait several (5~15minutes tops, usually) to get that first GPS connection. It should work much faster the next time you use it at the same location, though.
And to finalize, there is absolutely no reason for your GPS not to work outside the US, unless you had some kind of jammer with you =D. GPS works by receiving signals, it does not in any way communicate with anything else. If you did not get a GPS lock, you either did not wait enough, did not actually have GPS on, or the applications you downloaded had some problem.
cheers!