"Rekey" is a term which is usually employed when obtaining a new certificate: it means that you want the new certificate to use a newly generated key pair, instead of reusing the same public key as was in a previous certificate.
"Revocation" is the act of declaring, on the CA side, that a given certificate should no longer be considered as valid (it is a bit like having the certificate expire earlier than its nominal expiry date). When a certificate is revoked, its serial number appears in the CRL published by the CA (that's how the rest of the World is made aware of the revocation).
The two actions are mostly orthogonal to each other, but there are situations where you want both. In particular, if your private key was stolen:
You need to have the certificate revoked. Key compromise is the main reason why we need a revocation system. This should prevent usage of the stolen key to power a fake server (that is, assuming that the client browsers obtain and honour revocation information, which is a rather bold assumption).
Since the certificate was revoked, you can no longer use it for your own server (it blocks you and the thief alike), so you probably need a new certificate. And since the old key was stolen, you will want a new one, so that's a "rekey" situation as well.
Some CA will automatically trigger revocation when you ask for a new certificate with a new key pair; some other will not. Some will talk about the old certificate being "deactivated" which may be the same as "revocation", or could be something else (e.g. something like an account close on their side), depending on how much they abuse terminology. Any decent CA ought to have a specific procedure for key compromise which will do things correctly.