I think there's an awareness problem as well. Many teens don't think of legally downloading music as pirating music is what they've always done. It's not even necessarily thought of as wrong; after all, you can listen to the tunes on the radio.
About the only "well-known" services is iTunes' music shop, which has a fairly low reputation, and is fairly useless to anyone not using an iPod.