Yeah, that is very typical, at least, from my experience with americans. English with an accent is very difficult to understand for some people. Then again, unlike other languages, English is not spoken as it is read (like in Japanese, or Spanish), therefore accent is crucial, as redudant as this may sound (because obviously all languages have their own accent).