I'd bet the JIRA that Paul is pointing to is likely what's happening here. I'd look for read repair errors in your system logs or in your metrics (if you have easy access to them).
There are operations that can happen during the course of a query being executed that may happen at different CLs, atomic batch log timeouts (CL TWO I think?) and read repair came to my mind (especially for CL ALL) that can make the timeout/unavailable exceptions include a different CL. I also remember some DSE features causing this as well (rbac, auditing, graph and solr stuff). In newer versions of C* the errors may be more specific or a warning may come along with it depending on what is failing. Thanks, Andy
