Got my new phone this week; a Samsung/Google Galaxy Nexus. It's running the very latest Android 4.1, Jelly Bean, and I've put it on a Vodafone Smart19 Data plan. That gives me 500MB of data per month, with 50 minutes of free talk, and 5000 free texts. All for $19 a month, prepaid!
I get my old number ported over when the TelstraClear contract runs out on the 9th of December, so until then I'm carrying two phones.