You cannot simply put these two things together. One is the regular validation inside the ViewModel. The other are control-specific problems, like unconvertible values.
So there are two possible ways to solve this:
1) Don't use a converter. Just bind the string. Inside the ViewModel you can then use the validation to check for a valid value. (More MVVM)
2) Store your ValidationErrors on the controlside and merge them with the viewmodel errors. This is not easy but a good way to create one source for binding against ALL problems within your UI. We are doing this for complex textboxes at work. This means manual code in the controls but for complex customcontrols this is OK, I believe.
edit: just to elaborate a little on the 2nd point. We are having a DependencyProperty of Type ObservableCollection inside the Control. Then you can bind this Collection to a ViewModel Property and as soon as your control moves an Error inside the collection it is available inside the viewModel. You can then use this collection inside your validation implementation. This works pretty well for larger controls.
Edit2: For the MarkInvalid Stuff I mentioned in the comment. It would look like this:
DataErrorValidationRule validationRule = new DataErrorValidationRule();
ValidationError validationError = new ValidationError(validationRule, myTextBox.GetBindingExpression(TextBox.TextProperty)) { ErrorContent = "My custom message" };
Validation.MarkInvalid(myTextBox.GetBindingExpression(TextBox.TextProperty), validationError);
You would call in from inside a TextChanged when you can't convert the new given value or
Validation.ClearInvalid(myTextBox.GetBindingExpression(TextBox.TextProperty))
Maybe that will help?