same problem for my phone and my girlfriend's phone
Me and my girlfriend are getting the same error message on music box. We also tried looking up songs on music junk and no luck.
Maybe the feds cracked down on the sites hosting the songs
I'm rooted running on ics on HTC Thunderbolt
Girlfriend is on stock gingerbread HTC Thunderbolt