chances are you will still be there in may. alot of backpackers seem to get stuck along the goldcoast area, which is a pity as there is so much more to see in OZ,
If you can try to get away from the eastern states, its really huge country so be prepared for lots of travelling time between destinations. Some things you may want to check out up to the north (somewhere in the tropics, like Kakadu) and maybe some outback (I haven't been to Ularu yet, but i hear that it and Kings canyon are not to be missed.) also hmm theres not much to see in Adelaide (where i live) but Kangaroo island is amazing (especially the south coeast) and the grampians in Vic are pretty good too.
And dont forget to slip slop slap (you can spot tourists cos they're the red ones
Well enjoy your time and have a beer for me. I hope to be leaving OZ in a few months so it looks as if I'll just miss yo.