I got my SSL certs from Startcom and as you may know they charge for revoking. I am very angry about that ...
What would you prefer they do -- revoke hundreds of thousands of certificates? That would produce a certificate revocation list that some portable devices wouldn't even be able to fit in their memory. And then every time they updated their CRL, every device, even those on low bandwidth networks, would have to re-download a massive list. It's just not practical.
Is it possible to just switch from Startcom to another provider like Comodo, get new certs and change the certs on my server?
Sure, but how would that help? An attacker could still impersonate your server by using the old certs.
Could be there any problems with the old certs if they are not being revoked?
Yes, an attacker could use them to impersonate your server.
Is it possible to "block" these old certs on my server (Ubuntu 12.04)?
How would that help? The attacker wouldn't pass any traffic to your server but would instead interpose themselves.
The upshot of all this is that your security is compromised and there's basically nothing you can do about it. (Though it's a pretty minor compromise because it can only be exploited by an active attacker with at least some control over the network used to access your server. Also, you may have more serious compromises due to heartbleed, and many of those you can and should do something about.)