I worked with a lovely woman with a fairly strong Chinese accent. However, she was perfectly understandable, and one of our best reps.
We'd _still_ get people who insisted they just couldn't possibly understand her. I think some people just tune out the second they hear anything the least bit foreign. So, it might not be anything that is really his fault.
(Back when I answered the phone, I'd have people insist on talking to a man, because as a woman, I couldn't possibly know anything technical. It always cracked me up, because a lot of times, I was the expert in the category, so by asking for someone else, they were getting someone with less knowledge, not more.)