You would go through the relatively arduous task of decrypting and re-encrypting data for only one reason: you believe the crypto key has been compromised, but the data have not, or the reverse.
If both data and key were compromised. you're toast. No amount of key-changing will save you.
If one of key or data were compromised, it might make sense to change the key and re-encrypt the data in case an attacker might get the other half of the puzzle somehow. However, this smells like "change your password every 30 days, Just In Case.)
You mentioned one risk of decrypting and re-encrypting, namely a failure partway through the process. You mitigate that risk by encrypting to new media. But, of course, the old media remain, encrypted with the old key. You have to destroy both the old data and the old key with acid, fire, and strong magnets when the process is completed, or you haven't really mitigated any risk. If this is an online system, there will be downtime or a read-only period during the re-encryption process. There may be other risks.
If you somehow rotate crypto keys so that at any moment some part of the data are encrypted with an older key and some with a newer key, as suggested in another answer, then some of the data are exposed in the event of a compromise.
As Gilles has already written, this smacks of security theatre. Whoever is responsible for the policy should describe the risks that will be mitigated through implementing it. You can then examine the costs and the new risks introduced and make an informed decision.