Glad I'm not the only one with this problem. I can't people with accents in person either.

There is no solution though. The only thing you can do is ask them to use a better mic. I do all my conference calls over Google Talk and use a condenser mic, which is good for other people hearing me but doesn't so anything in the reverse direction.