Been there, done that.

Since I moved to Australia plane fares within the country have gone incredibly low, don't know about to New Zeland, but once you're on the East Coast it should be pretty easy to get anywhere apart from the West xD