Another vote for Flyinn. We did South Island with them 2 years ago and will be there again next month to do more flying with them in both South and North Islands - including Wings over Wanaka. Absolutely outstanding.
To get your NZ validation you must have at least 5 hours of instrument flying in your logbook. That's the only "gotcha" that I can think of. You must, of course, be very aware of the weather and how it affects flying there. We are not used to mountains in the UK and I certainly learned a hell of a lot on my first trip.
Have a great time!