There are a lot of studies out there that show that people only "hear" the sounds that they heard as a child. So someone who grew up in the countryside in Japan is going to have a hard time speaking English "properly" even with gargantuan effort.
Anyone here who's spent a decent amount of time abroad probably knows what I'm talking about. When someone asks you how to say something in English, and you say it, and they repeat it but it just sounds off, and they're incapable of producing the same sounds as you. It seems like the simplest of exercises but it hits the core of the issue.
For any Americans, trying to learn something like Thai (or other tonal languages) can be extremely difficult because of the tonal information. I am pretty incapable of producing anything sounding correct in Thai no matter how many times my friends try to make me say it.
You also have probably heard French people speak English. There's not much else to say about that. Almost all the accent is derived from differences in the sounds between the two languages.
Saying that it "just" requires effort is underestimating the amount of time it can take to rewrite the way you speak. People living years in foreign countries can still end up speaking with strong (yes, even near incomprehensible) accents, and I've run into a good amount of them.
There's a big perception penalty when you're not "in sync" with the language you're speaking in, which is where you get the "people talk slowly to you and assume you're not very smart" effect. So character judgements on language ability is a bit much.
There's an easy solution though: just hire somebody who can speak well. They're harder to find in some areas, but it's a pretty high priority. Just don't hate on the CEO if he can do his job.