Yes, Paralell imported are selling iPhones, and if you ask them "yes" they will "unlock" them for you, so you can use them with NZ's selection of telecommunication providers.
They will even upgrade your old iPhone's firmware to the latest version if you take it in to them and pay a very small service fee. (I think it was like $15-$22)
And yes you can upgrade the firmware on a older firmware "unlocked" iPhone yourself if you wish, you just have to follow the correct steps.
richgamer: and what happens when vodafone nz gets the iPhone. will people be able to use itunes to update the firmware from apple which will include vodafone nz's profile in the firmware?