ajobbins: I used Vodafone for many years, mainly in Wellington and Auckland. I had no end of issues with Vodafone coverage, especially in Auckland.
The solution was to change to Telecom XT. Better overall data (More stable, lower pings, faster page load times on web) not to mention better quality calls and far superior coverage.
+1
Although it is not fair to say telcos should provide good coverage everywhere (because it is simply impossible), but after years of bad VF coverage out west (I have almost nil coverage at home), I finally moved to 2degrees.
Even I cannot get 2degrees 3G coverage at home, at least I have a decent 2G coverage so I can do voice calls without shouting to the other party.
VF coverage is so bad I cannot even my phone in Westcity Countdown. You can try it yourself: take the phone to the far corner of the supermarket where they sell chilled drinks/water, and you will know what I mean.
Another blind spot is the Vodafone shop in St Lukes (the one next/close to 2degrees). I was there looking for a charger when I got a call from my wife. She could not hear me, so I check the signal of my phone, then my phone shown no bars in terms of coverage.
By the way, XT/Skinny coverage is great at my home. My wife is now convinced to moved to Skinny, just waiting for her number to be ported.
=-)