I have had good luck so far using myspace.com to find some real treasures. I actually have had a leg up on the 2 bands/groups I have talked to, as I knew 1 of the members from each group from other communities I have belonged to. Also, try to find bands that are signed to small (indie-type) record labels, not a band that just "freeballs." The reason is because its a little more professional, which is better, imo.
Sample experience: A guy who was a mod at a community I had been part of for over a year had a myspace link as his sig. One day, a couple months ago, I was bored and decided to click it. Turns out he is a rapper in a California group. They are very organised, and very good. Not to mention, there are exactly 0 rap groups that are any good here in Cincy (that I know of anyway). They had 3 songs posted on their page, I listened, I was impressed. So, I sent the said mod a PM and found out he was interested in helping me out. I got in touch with his Producer, then his label. I think the Producer was even more excited than me. I sent him a sample avi file so he could review my style-quality and he agreed to let me use some music in future projects. He is uploading a full CD for me to comb through. For $40 per 250 units sold- per song used- (festival and personal copies dont subtract), I now have a professional quality rap group in my arsenal. Not to mention a free CD.
Like has been said here many times, I found being honest and sincere helped me reach a nice agreement.