To answer your question - very much so.
The only way to overcome this is lots of listening. I can\'t think of any other way to \"learn\" how to understand the spoken language. English has an extensive number of various accents and pronunciations and some of them can be extremely hard to understand, especially for a non-native speaker. Again - the only remedy is to listen as much as possible (even though at the beginning - as you noticed yourself - it will be tough and you won\'t understand that much).
A good exercise that I\'d recommend would be to record some TV show or a movie, watch it (trying to understand as much) and then watch it again with closed captioning on and compare what you see to what you hear, and finally watch it one more time - without closed captioning to see if more words sound familiar.