I have seen The Mars Volta mentioned twice in this thread, and I must make a third mention.
I don't wish to resort to hyperbole, but their most recent album, "Frances the Mute," is the best album I have heard all year from any genre.
The band was in town last week and they were killer. Even with a less-than-average sound system the band made wonderful extrapolations on the album originals. A somewhat unorthodox line-up was heard: reedsman playing bass clarinet, tenor, flute & percussion, a conguero, keys, bass, guitar, drums, & vocals. The drummer has spoken of his disparate influences from Elvin Jones and Tony Williams, to Billy Cobham, Tony Allen, and Bill Bruford. And John Bonham.
The music itself is a shifting prog-rock / hardcore thing, with some 70s heaviness and salsa thrown in for good measure. Maybe some Krautrock, too. The prog thing scares many folks away -- don't worry -- they aren't Yes. Sure, they are prone to Fripp-like angular guitar excursions and EAI-sounding bridges between tunes. The lyrics in both Spanish and English are nonsensical but very interesting. Words for the sake of words. Almost like he chooses the words for how they sound, rather than what they mean.
I read this review on somethingawful.com that was funny as per usual, but also inviting. I immediately went out and bought the record.