Based on simple statistics, I have to wonder whether the problem was that they were hard to understand, or that you are bad at understanding them.
Not to mention that it *does* take practice, of which I've had little. There are coworkers I have who work with India contractors on a daily basis and who don't seem to have my difficulty; then there are people like me who may speak with them on job-related issues maybe once every week or two and who are as hard-pressed as I am to grasp what they're saying. (Case in point: conference call this morning, the project leader of a project I'm involved with was darn near interpreting for the other three of us in the room as the call progressed.)
I freely admit that it could be that in some way my brain is just wired such that it's harder for me to make the cross-connections than it is for other people. Or maybe I have some subconscious resistance for making the effort.
For something like this, early exposure to foreign languages may help. Nowdays I half-wish my parents had insisted I'd taken French in the grade school I went to. I had German in high school and can usually puzzle out the meaning of a German web site or news group, but that's not quite the same as intensive exposure at an earlier age.