Yeah, heh, thats the thing... They've been meaning to be up and running by now about 5 times since 2002 or something from memory.

Several issues with hardware etc. A lot of info on them here: http://www.geekzone.co.nz/forums.asp?ForumId=85
You will see from the above that they were having all sorts of issues lifting off. But, looks like they're still going ahead. According to one of our guys here, they've already started the testing etc and comm towers are going up at a rapid rate.
Looks like Telecom aren't too far away from their new network as well: http://www.telecom.co.nz/newnetwork/