Thank you for your replies 🙂 I did try uninstalling the agent, restarting and reinstalling, but I just got the message about the device being managed.
The profile was not removable, so yes, I have erased and set it up again.
I think the issue was, as ekramer suggests, the signing certificate has been updated in the system, so ultimately it's better to have it erased and reset with the new certificate.
Happily, our deployment profile takes care of a lot of the fiddly stuff, so setting up the new user account will be a snap!
Cheers
Rachel