Apple have a toll-free support line, no surprise there but, it can't be called from Vodafone.
The number is 0080076667666 which isn't in the standard New Zealand format, although it does work from any Telecom line.
Please fix it Vodafone, Apple or whoever's job it is to fix stupid problems like this.