What is Cβ (C-beta) deviation?
Just browsing through this "Unanswered Question" now (in late 2014). I hope it's not too late?

In protein structure validation, Ramachandran outliers are a strong, but not absolute, indicator that the backbone confirmation of your protein structure deviates from all the high resolution structures known to date, and hence need your attention during the progress of refinement. 

If all the phi-psi angles (backbone conformation) all fall into the "allowed/favoured" regions on the Ramachandran plot, your structure model is probably, but not necessarily, esp in the case of low resolution, correct. Hence there are other weaker criteria in protein structure validation, and Cbeta deviation is just one of them. In the light of high resolution structures out there, it turns out that Cbeta also has a favoured range of dihedral angles, suggesting that any misfit between your structure and the "probable" side chain-backbone conformation also deserves your attention during structure refinement.

In MolProbity, the justification and validation procedure are described here.