We consider counterfactual explanations for privacy-preserving support vector machines (SVM), where the privacy mechanism that publicly releases the classifier guarantees differential privacy. While privacy preservation is essential when dealing with sensitive data, there is a consequent degradation in the classification accuracy due to the introduced perturbations in the classifier weights. Therefore, counterfactual explanations need to be made robust against such perturbations in order to ensure, with high confidence, that the explanations are valid. In this work, we suitably model the uncertainties in the SVM weights and formulate the robust counterfactual explanation problem. Then, we study optimal and efficient suboptimal algorithms for its solution. Experimental results illustrate the connections between privacy levels, classifier accuracy, and the confidence levels that validate the counterfactual explanations.