I got my SSL certs from Startcom and as you may know they charge for revoking. I am very angry about that ...
O que você prefere que eles façam - revogar centenas de milhares de certificados? Isso produziria uma lista de revogação de certificados que alguns dispositivos portáteis nem seriam capazes de colocar na memória. E então, toda vez que atualizavam sua CRL, todos os dispositivos, mesmo aqueles em redes de baixa largura de banda, teriam que baixar novamente uma lista enorme. Não é prático.
Is it possible to just switch from Startcom to another provider like Comodo, get new certs and change the certs on my server?
Claro, mas como isso ajudaria? Um invasor ainda pode representar seu servidor usando os certificados antigos.
Could be there any problems with the old certs if they are not being revoked?
Sim, um invasor pode usá-los para representar seu servidor.
Is it possible to "block" these old certs on my server (Ubuntu 12.04)?
Como isso ajudaria? O invasor não passaria tráfego para seu servidor, mas se interporia.
O resultado de tudo isso é que sua segurança está comprometida e basicamente não há nada que você possa fazer sobre isso. (Embora seja um comprometimento muito pequeno, porque só pode ser explorado por um invasor ativo com pelo menos algum controle sobre a rede usada para acessar seu servidor. Além disso, você pode ter compromissos mais sérios devido ao heartbleed, e muitos deles deve fazer alguma coisa sobre.)