I saw Kataklysm live, and I wasn't that impressed. It wasn't like they were a bad band or anything, just not special. I heard a couple of songs from Devildriver and I was really suprised with them. They weren't all that bad, but they sounded like "My First Death Metal" music.
Still, I think that Kataklysm would have been a much better choice for the Opeth tour. The crowds at these shows are going to suck with all the nu-metal kids who are going there because Dez used to be in Coal Chamber. The Opeth crowd is too sophisticated for them.