Well, phone data settings are discussed already so apologies for going over it again...
I just got off the phone from a rather unhelpful vodafone CSR who told me that to use data with the HTC magic, I'd need to get on a special "HTC Magic" contract, and I couldn't do it at all with prepay.
Finding this a bit hard to believe, I went into settings|wireless controls|Mobile networks|access point names, and added an access point with the APN of www.vodafone.net.nz ... tada, it works.

Now, is this the correct way to do it?
In theory I should be setting MMSC to http://pxt.vodafone.net.nz/pxtsend  as well, anything else I'm missing?
Vodafone's site is a joke.... apparently they don't inform their helpdesk staff very well either.
Cheers for any help.