Please note you made a typo in (a), where you wrote "They made an mistake..."
After making that correction, I think (a) and (b) are fine: in (a), you couldn't believe the mistake they made, while in (b) you couldn't believe their having made that mistake, i.e. the fact that they made it.
(c) is wrong because there is a duplication of the object:
c. They made an error (that) I couldn't believe they had made it.