<Chappo hops up on the soapbox>
I'll add my $0.02 while I have a spare
minute (edit: okay... that took a while);
What makes an 'English Beer' English - does it have tea and scones in it?
What makes a 'German Beer' German - is it particularly productive?
I doubt that when Pilsners were being created people thought 'what would be particularly Bavarian about this?' - they were using a new technique (lagering), and that gave the beers a distinct character. English beers aren't low carbonated because the creamy head reminds them of fog. I find it odd to try to force the idea of a (new) 'Australian Beer Style' by randomly introducing 'Australian... things'.
Apart from the argument of 'why does Australia even need a style?' - a respectable style should come about naturally, and be identified as 'Australian' because that's where it originated - why should you not be considering a large proportion of the English ingredients? A style that comes about naturally in Australia will probably have English roots.
As for Australians being big beer drinkers, that's a bit of a stretch. Other countries are proud of their world-class beers, exported and respected globally. As Aussies we (as in, the general population) seem to be overly proud of the mainstream swill produced for local consumption, but you wouldn't put it out to play with the big boys. Sure, craft brewing is taking off in a big way, but it's still very much a minority, and ignored by most of the population. The term 'craft-brew' is actually known throughout America, and these beers are sought-after, not just stumbled upon.
Now I'm all for craft-brewing, but I think this is where you'll need to look if you're ever going to see something 'Australian'. Even then, any 'new' style will likely fit somewhere in between BJCP styles, so it will be 'a bit of English with American notes', or whatever. As homebrewers we can play around with new techniques - and I believe that this is where those techniques will be developed - but those techniques will need to be picked up by micros before they get any good recognition.
I'm not trying to (entirely) discourage you, but rather make you think about 'what exactly it is that you're trying to do.' Although you'll likely make something quite nice with an interesting range of ingredients (and that's a great achievement) I think if you want to make 'a new style' you'll need to start looking into turning the entire process on it's head, and producing a new technique that gives a beer a distinct quality. Think what decoctions did for German beers. That may or may not come about by random trial and error, but education (one of the main reasons many people frequent this forum) is a great place to start.