I would look around for a provider that has been around for a while. At least 5 years is a good amount of time to know that they aren't as likely to just disappear overnight. You are best to email them, and see how good their response times are and how well they handle your questions.
I've had VPSes with a lot of providers, and here's my opinions on the NZ ones.
RimuHosting Incredible service, decent pricing, good customisability. I've met all their staff, great people. 24/7 support, incredibly fast and helpful. Hosted in the HostingDirect datacentre though, which isn't known for its reliability. Unusual to have less than 30min of downtime in a month. Would recommend if you're not hosting anything mission-critical.
SiteHost Good service, decent pricing, but completely unrecognisable. You can't add more RAM to an existing VPS, you have to upgrade your entire plan, even if you don't need more HDD or bandwidth. Incredibly reliable. Have only ever once seen an unscheduled outage which was a catastrophic failure that couldn't easily have been avoided. Highly recommended for mission-critical.
HostingDirect If all you're after is something to play with or host a Teamspeak server for your gaming clan, this'll do. Their reliability is bad (as above), and they have no support whatsoever outside of business hours. Ridiculously cheap though.
OpenHost Had a Windows VPS with these guys (others were all Linux). Didn't have it long enough to form a real opinion, but had no outages in the 2 months I was there. Support can be slow at times.
Good luck finding any kind of decent NZ based VPS for what you want for that budget!
For that price, you could get a linode in Fremont, CA which would give you 20GB storage, 200GB data transfer (outgoing), 512MB of RAM and access to four cores/threads, plus good reliability/uptime, support and it's Xen, instead of some OpenVZ crap.
People! This is a positively antique thread from years ago (shouldn't this have been locked?)
Anyway, ignoring "NZ Based", Amazon EC2 instances are pretty hard to beat for convenience, flexability, and price, of course completely and utterly unmanaged though.
Pay only for the hours you use it. If you can run as a "spot" instance (even just setting a really high bid price) then you are really paying ridiculously tiny amounts for the instance run time (often a fraction of a US cent per hour, crazy).
I have a number of sites I manage on EC2, even just a "micro" instance can run a modest website, and if you do your architecture right, scalability can be as easy as firing off some more "micro" instances behind an ELB (Elastic Load Balancer). One of my sites uses a single "large" instance as a "master" and depending on demands a bunch of "micros" as slaves, most of them on spot pricing, all behind the load balancer.
In short, EC2 and ELB make a really smashing setup - if you don't mind having no support.