Well, Vodafone has just announced that they have signed an agreement with Apple, and will be supplying the iPhone to NZ customers (and 9 other Vodafone countries).

No date given, other than some time later this year.

We should find out more, after WWDC (June 6) and announcements about 3G time frames and release dates.