I've come to the conclusion nearly any type song would work for a music video. As for that movie, I never saw all of it so I've no idea (it seemed odd after my normal anime). But if you're looking for a place to get mp3s (evil things, I know, but we can't all afford nice cds to get the songs from) you could try:
http://www.mp3dimension.com
There isn't so much popup-harrassment as other places, and if you've got DAP, you can type the urls in directly without messing slower downloads (think resume capabilities).
If you're short on appropriate songs, I find it's fun to download (or rip from CDs if you have them) every song I spot and then run through them until something catches my ear and can be linked to appropriate footage - which also works if you have the footage and are looking for something to match it, assuming you have a large enough collection of songs.