I think it's more of an instance of "it works on my computer"; not testing on an environment sufficiently similar to production, and applying a change that cannot be rolled back.
This is the key. The rollback mechanisms were broken. Re-encrypting data is incredibly scary because if you lose the new key you have effectively lost your data. It is important to ensure that you have up-to-date backups of the previously encrypted data and key before you start.
A better solution may have been multi-key support. Some test records could be encrypted with the new key and the system let run for a week or so. Then all new records could start being encrypted with the new key and run for another week. Once everything looks good a background job could be started to convert all data to the new key. Then the old key can be retired (other than as needed for backups).
Although they did have the key printed in an envelope, so it sounds like that would have been an effective recovery solution once they remembered.