I was mistaken on what number to drop when calling me from the states, you have to drop the 0 infront of the 4. (NOT the zero in front of the 1)
My mobile number is:
(04) 0173 0508
From the states, you dial (011) to get international, (61) for australia, and then the number:
011 61 (4) 0173 0508
BTW: Pricing on cellphones just got nicer, it turns out that all inbound calls (even international ones) are free.