I really enjoyed using Songza between it's intermittent outages. The concept is well executed, the UX is polished, but performance-wise it just doesn't seem ready for prime-time. In fact I got to this page by googling 'Songza down'. :-(
a bit of perspective for those thinking Songza came out of nowhere and stole Pandora's thunder.
Songza was created in 2007 by Aza Raskin and Scott Robbin. It was a music search service back when that was a popular meme. It was bought by Amie Street in '08.