Telecom and NZ Comms are working on there GSM networks. Where I live (rural) I get dodgy reception from vodafone, but when doing a search in the carrier selection menu Telecom NZ appeared. Tried connecting to it and obviously failed but for a second my reception bars went nearly full and the EDGE icon appeared! For those that don't know EDGE is enhanced GPRS and is capable of much faster speeds not sure how fast though. Vodafone skipped EDGE and went straight from GPRS to 3G.
And iPhone 3Gs are having slight problems at the moment.
Apple has these issues when they release new products but they always fix it in the end.