VHA have been making a concerted effort to improve coverage and the "customer experience", and have been investing heavily in new sites and improving existing sites. They have also just proposed another joint venture with Optus to take on Telstra's dominance.
(I work in the industry over here, so have an inside track)

In saying that, the back-office systems and customer service over here in Aus is rubbish - getting better, but with a long way to go.

My wife and two sons are all on VHA (I moved to Telstra with my new employer), all with iPhones and pretty good value:
Lovely wife and boy 1: AU$29 pm; $180 worth of calls and 200MB. Payback on the mobiles is $5pm (iPhone4), $20pm (iPhone4s) on 24 month plan.
Boy 2: AU$45 pm; "infinite" calls and texts, 500MB.

I made sure both the boys took the $10pm insurance.

My only gripe is international data charges. With one boy in SE Asia and the rest of us in NZ for a week, monthly bill was AU$675!! All of the extra costs were roaming (international) data costs.