I was having the same error.
CUCM, CAPF and CTL service was running which i turned off. After deleting the Phones when i tried to re-register the phones they started to give me this error. "Registeration Rejected : Security Error" . I also switched the tftp from Publisher to a subscriber server.
Solution : I manually added each phone to the system since they were few phones. You can Use BAT to add the phones if you too many phone having the same problem.
Hope that helps
If any one figure out why it happened please share it here.
Thanks
Regards
Mazin Muhammad