I have been living in Australia for 7 years now, and still haven't been able to pin down the local regional accents. I can tell a "Town" from a "Country" accent, but I can't reliably tell which state a speaker comes from.
The only shibboleth I am aware of is "The Melbourne Noy" which is how some but not all Melburnians pronounce the word "No". Also, think of Kath from "Kath and Kim" saying "Look at moi, look at moi!" Unfortunately, this pattern isn't restricted to Melbourne or even Victoria.
So does anyone have any other tips for recognizing Australia's regional accents?