As the thread seems to have moved into random genres at this point... I figured I'd plug a few decent local bands that come immediately to mind. Some of these have been mentioned in other threads, but I don't think they've been listed here yet. Links are all to either youtube or myspace for examples of the music.
Random: Laura (how has this not been mentioned in this thread yet?) - Pretty Post Rock
Six Ft Hick - Rock. One of the most fun live bands in Australia.
The Necks - Hour long beautiful, if slow, improv jazz pieces. (link is to ABC tv site, with a streamable set of theirs.)
Yves Klein Blue - Really not my style, but I'll get slapped by some friends if I don't include them. Kind of perky... ummm rock/pop?
Metal:Astriaal,
Five Star Prison Cell,
Dead Letter OpenerExperimental:Ben Frost (admittedly he lives overseas now, but still...),
Ai Yamamoto, Lawrence English/IO (*grumble* appears he doesn't have any viable linkable music) so
www.room40.org is his label, as a compromise, Chris Abrahams (pianist from The Necks), Pimmon
I'll second Martin Martini and The Veils by the way (although The Veils kind of count as a UK band at this point imo). I'm sure I'm missing a ton, but meh.