Listening is difficult. You need to do it at the speakers speed and you also need a large vocabulary. You need to be able to process different voices and ways of speaking. (even in English I can have difficulty with accents and it's my native language!)
Of reading, writing, speaking and listening I think it's the most difficult. It also gets neglected in favour of written work because that is easier to access in many ways.
I count myself lucky if I get 60% of what is being said to me. And it takes a LOT of concentration.
What I found helped me was talking to a native speaker. Although an hour or so is about my limit for "Japanese only".
If you don't have anyone local, you can use Skype to talk with someone living in Japan.
If they are good they can drop the level of their speech to nearer your level. They can repeat things and rephrase things. The topic can be something you know about and have a vocabulary for.
It's a slow process but eventually your ear will start to tune in to Japanese sounds and pick out the phrases you do know.
Part of listening skills with a second language is "getting enough". You don't have to understand everything, as long as you can pick out what you need. (Of course, understanding everything is better)
Another thing that can help with listening is Shadowing. This is where you repeat sentences in a recording. The ideal is to be able to do it in time with the recording. In early stages you'd use a transcript to help you understand. Although primarily an exercise in speaking, it helps train you to hold and process larger chunks of Japanese at one time. When I started single words were difficult, now I can often speak back sentences.
www.iknow.co.jp a site mentioned here recently, has an interesting dictation feature you might also find very useful. You type in a sentence that is spoken to you. It then highlights what you've gotten wrong and you try again. You get three tries in about 30 seconds or so. And it rates you, although not knowing it's criteria I can't say how accurate it is.
Listening to Japanese TV news magazine shows is good because an awful lot is subtitled, about half the screen is taken up with text. Or if you can get DVDs from Japan you can listen with the Japanese subtitles turned on. It's easier if you already know the plot or have watched it in English already. A single scene is probably enough to start with.