Galaxy S network issues on Vodafone New Zealand
After fiddling around with some of the settings I finally found a solution for my phone. (It was still able to access the web through the browser, but couldn't use the network for Google Maps, Twitter for Android, etc.):
Under Settings -> Wireless and network -> Mobile Networks -> Access Point Names I found "VF MMS" and "connect."
"VF MMS" was ticked. When I ticked "connect" instead, everything starting working again. (I don't remember altering this setting before, but I may have done so, or maybe some app I installed changed this setting.)
So for my Samsung Galaxy S Vibrant from t-mobile in the U.S., setting it to "connect" makes Google Maps, Twitter and other apps work well on the Vodafone network here in New Zealand. No more "network connection lost - retrying" messages.
I hope that saves someone from having to figure this out all over again. The guys at the local Vodafone shop weren't aware, so I've let them know as well.