Or kep your device and swap the SIM card
If you're happy with your old phone (my Sony W880i is going strong, and it is basically a skinny W800i) then another option is to keep the phone and ditch Telstra. They're trying to get out of GSM anyway, so it won't be long before 2G phones won't work at all.
My Motorola 3200 International still works with Vodafone, and you can't get an older GSM handheld phone than that!!!