There is a cool place in Sydney Australia if anyone ever comes down here! The Basement which is right in circular quay (near the big Opera House) which has a bit of everything but it has a good atmosphere and good history (at least wrt Australian venues).
http://www.basement.com.au/
If Vince Jones is playing when you're there, you're in for a real treat.