The problem is how Windows uses the system clock compared to how Mac OS X does. OS X sets the system clock to UTC and converts to your time zone, whereas Windows sets the system clock to the time in your time zone. When they update their time from the Internet, it will change to the correct time in both. In your case, it seems that OS X is taking its time to update the clock to NZST, so it's adding 12 hours to what Windows has set the clock to, moving you 12 hours into the future (it'll be worse when daylight saving is on, pushing you 13 hours ahead!).
As simsaladimbamba, you need to check that setting in Date & Time System Prefs pane. If it's not ticked, then tick it. If it is ticked, then OS X isn't connecting to the network fast enough to update it. When it happens, ensure that you're connected to the net, then untick and then re-tick that option. Hopefully it won't take much longer to update (I used to have this problem all the time with Tiger, but I've found Leopard and SL to be much quicker at updating, so I never have to do it myself).
EDIT: I see you've already tried this.