I just saw something on 3news regarding this, a company which has backing from the french government running 2 cables from auckland to noumea and one to Australia with a link in there to Hawaii. They just need a major Telco/ISP to be a long term customer first (I did hear TelstraClear mentioned)
So if Pipe goes ahead then NZ could have 3 links overseas within a few years :)