I've been using StartSSL for my ssl certificates because they are extremely cheap. They provide standard ssl certificates for free. They also allow you to validate your identity, after which they will allow you to make wildcard ssl certificates for free.
The catch is that revocation is not free. Normally, I wouldn't find any sort of issue with this as having to revoke your certificate means that you did something wrong. It seems perfectly reasonable to make people responsible for their mistakes. In this case, an exception should be made in this case since not revoking the old certificates is bad for the public. StartSSL has chosen to not make an exception in this case.
Because of that decision, I've switched certificate authorities. I'm now using Gandi. I am also removing StartSSL from my trusted CAs. I would suggest that you do the same.