Jamendo - music licensed through one of several Creative Commons licenses or the Free Art License (Search > Advanced search). Sometimes there's a problem with downloading as Ogg Vorbis, but there's a work-around with a direct URL.
Wikipedia list of full length copyleft/public domain musical works available on Wikipedia or Wikimedia Commons
incompetech: CC-BY music by Kevin McLoad (including piano recordings of public domain classical tunes), searchable with a tag system by genre and feel.
Altermusique.org: music following the Free Music Philosophy; while the FMP accepts "non-commercial" licences, Altermusique.org provides Art Libre, CC BY-SA and CC BY songs, searchable by license.