Apparently 3 in Australia uses 3G 2100, sharing the NextG Network with Telstra.

And.. quote wiki "In areas not covered by 3's 3G network, customers roam on Telstra's GSM/GPRS/EDGE or UMTS networks."

Edit: Apparently 3G won't work on Telstra, which would include Three i'm guessing

Quote nokia forums "If your network is Telstra then the N900 will not "do" 3G for you since Telstra chose to use the 850 MHz band commonly used in the US. Most networks in Oz use 2100 and 900 MHz like the rest of the world." So.. choose Optus / Virgin.