Telstra is the only carrier that will give you reasonable coverage throughout Australia.
Unfortunately, despite all the hype 3G does not have the range or coverage that is advertised.
Telstra comment - ' you may have to move around a bit to get a signal '
I understand that not all the aerials have been installed and correctly tuned - yet.