Yeah 3 decided to be shitty - just like Telstra, Optus, Vodafone, etc.... Mobile phone companies run phone networks on specific frequencies different frequencies have pros and cons much like AM and FM radio.
This is the same for 2G and 3G networks. However because 2G networks have been around for a while most phone's manufactured today are 'quad-band GSM' e.g. they work on all 2G frequencies in use. As 3G networks are relatively new most phones only work on 1-2 frequencies.
So in short you need to pick a phone which will work on your chosen network, so what are the frequencies?
Telstra NextG UMTS850Mhz
Optus/Vodafone proposed extension UMTS900Mhz
Optus/Vodafone metro areas UMTS2100Mhz (masked to appear as two networks is actually just one)
Telstra 3G / 3 mobile UMTS2100Mhz
Then there are roaming agreements between providers, for all providers if your 3G coverage drops out the phone will roam onto 2G coverage, which will make calls but the internet is slow and expensive. Note: 3 mobile is scheduled to start roaming onto Telstra NextG from April, contact 3 for details.
So all up you need to look for a phone which supports UMTS2100Mhz, if the budget stretches to a dual-band I'd suggest an 850/2100Mhz combo as it will give you good options in Australia and when travelling overseas (europe/asia has good 2100 coverage and the USA is rolling out 850).