I have the same experience as you. I have been working with many non-native English speakers from different countries, and Americans (and to some degree Brits) are usually the ones who can't follow what is said. This improves over time as they get used to different accents, but it seems it is easier for non-native speakers to understand foreign accents than native speakers in general.

I'm not saying I always understand 100% of what is said. When someone with an accent from a specific part of a country speaks super fast and is on a poor line with lots of street traffic in the background, it can be hard to follow. But usually I catch enough of it to be able to communicate.