Just thought I better post this as Vodafone don't seem interested in letting their customers know. 

If you want to connect to a VPN with an iPhone (when using cell data), then you need to change your default APN to www.vodafone.net.nz.

The standard iPhone www.iphone-vodafone.net.nz no longer works with a VPN.

http://forum.vodafone.co.nz/topic/9432-vpn-over-3g/page__pid__73321__st__0&#entry73321

"Please be advised 
www.iphone-vodafone.net.nz is no longer supported for VPN connectivity , 

we can support www.vodafone.net.nz for L2TP PPTP IPSec , this is what the Iphone will default to when used in a tethered scenario .
The default APN on your iPhone needs to be changed to www.vodafone.net.nz to support the above .

Reason :- Vodafone is always looking at ways to improve network and security.

Vodafone are currently looking at further changes to include support for PPTP protocol however at this time we cannot suggest a deployment date.

Damian "