I'm an American English speaker, and during many visits to the United Kingdom, I grew accustomed to the different accents in British English (that is, people in central London spoke differently than those in Liverpool or Manchester, who spoke differently than those in Leeds, etc.) But when I took a Beatles bus tour in Liverpool and was seated next to an Australian, I had to struggle to understand him. His accent was completely different from any other BrE dialect I'd heard. To my ears, it sounded as though he kept his teeth firmly clenched whenever he spoke.
I'm sure BrE speakers will have their own, more precise, descriptions of the Australian dialect, but that was my experience.