gregdane: You have some of the numbers wrong. New Zealand uses 900 and Australia 900 and 1800. Very few countries outside the Americas use 850. There's a useful list here (scroll down toward the bottom):
http://www.thetravelinsider.info/roa...bandphones.htm
However, I think you still have the same problem, because the Samsung x495 has 850, 1800, and 1900.
By the way, the Vodafone NZ prepaid SIM has quite good rates when used in Australia.