I've spoken to some americans who can't tell the difference between English and Australian accent its not that difficult.
How big is the regional variation of accents in the states and in Oz. I occasionally have trouble with yorkshire and newcastle type accents but not often, some people from liverpool just talk too damn fast, although they could all be on speed I suppose.