Hi Matt,
There are the odd shops around where you can buy fixed gear bikes -
the Masi brand seems to be available in both Auckland in the North
Island and here in Christchurch in the South Island. Otherwise, you
might be better off working as a mechanic and building one up at the
shop.
Regarding touring, the South Island is by far the prettiest (that
should get some replies from people in the north)!!! There are many
more mountains and far fewer people - scenery ranges from damp fern
forests to desolate arid areas, all within quite a small distance.
The sun in summer can be very harsh - February is the hottest month.
Of course right now (July) is as bad as it gets - it's presently
howling a gale outside and can't make up its mind whether to snow,
rain or sleet (it's done all today to far).
I have heard on one person touring NZ on a fixed gear before - they
used a trailer for luggage.
Regards,
-Martin