Changing a certifcate+key algorithm by dropping & recreating with the same names
Just to feed back on this, the process worked fine and the data was re-encrypted successfully.  

Therefore despite some concerns raised over symmetrical data encryption, (of which there are business rules to justify this), all worked well.  

All stored procedures that reference the key continued to work fine without any modification being required.