I have seen very few phones that support both UMTS 850 and 900.
Is there a map of where NZ cell providers support UMTS 2100? Most 3G phones appear to support UMTS 2100 whether or not they support UMTS 850 or UMTS 900.
My own HTC Magic android phone can happily use Telecom's XT network provided I'm in a UMTS 2100 coverage area (which i usually am, at home and at work). This is despite the phone not supporting UMTS 850.

