Just did a restore from iTunes and it seems happy with Wellington now and emails arrive in the correct timezone.
Anyone else have this problem - I had issues getting the phone running in the first place so maybe it's related. I had "no service" from day one, told to wait 3 days for the number port to go through, then still nothing - numerous calls to vodaphone, 2 complete erases and restores. They finally told me to go see a "real" person at a store and it turns out the online store shipped the wrong sim card with the phone i.e someone else's - 30 seconds later with a new sim and the phone worked so maybe it got confused about where it was when it was first activated.
Maps and weather now default to NZ and the GPS seems a lot snappier at finding me as well.
On the plus side, I've typed in my 128bit WEP key so many times I can remember it - shame they don't provide a hexadecimal input mode for wireless passwords.