Put a book in front of me, I can get it. Let me listen to someone speak it and I am lost.
Any ideas on how to conquer that fault?
Listen a lot, as often as possible. Watch TV and movies - there are many on Youtube and Youku. I like to convert interviews from Youtube into mp3s and listen to them during the day during down time. Pick a character in these shows and try to imitate their accent (stick to someone your own gender). Try not to read the subtitles (even the Chinese subtitles).
If you want to go further, strip out voice clips from these TV and movies and put them into an SRS system (Anki, Mnemosyne, etc...).
Some of the links are outdated, but there's a ton of info there, including descriptions, vocab lists, difficulty rankings and more.
Use a tool like Audacity: http://audacity.sourceforge.net/
Find a recording of a native speaker that has a transcript.
Listen to a section of the recording.
Record yourself saying the same thing.
Listen back to your recording for mistakes and problems.
Repeat the record/listen cycle until you are happy.
Move on to the next segment.
Finally the most important part and key to the whole thing: do it every day. If you do 30 mins of this a day then you'll notice minor improvements after about a month and significant improvements after about three months.
Also, a shameless plug, check out http://www.chinese-forums.com/ which has a load of advice for learners of Chinese.
And my own tools for learning Chinese:
The key is to (1) watch/read/listen to stuff you truly love, and (2) make a sustained practice of it.
You have to socialize in the language, that's really the only way to learn it.