Things are somewhat better, but far from the speeds we see in the more developed parts of Asia. I'm in Wellington, and get 3.5 M.bits/second downstream, with a 50 GB monthly usage cap.
There is fibre around the Wellington CBD, and it extends outwards to some residential. There's also a cable TV offering.
The rest of the country has to put up with ADSL and Wifi links... though things may have improved in my 2 years away from home.
The entrepreneurs behind it are a good team; I've worked with Rod Drury for a couple of years at his startup, so I know this was something they've pitched national government before. It will be interesting to see what sort of public help they get with the endeavor.
New Zealand has traditionally been a leader in internet uptake - see the BBC's recent data visualisation http://news.bbc.co.uk/1/hi/technology/8552410.stm The initial uptake was all dialup, however, and we've been left behind in the push to broadband because of a local monopoly/duopoly.
I hope this cable goes through - I may consider returning home one day :)