During the installation of new Cisco phones, I received the message "Registration Rejected : security error" as soon as I connected the phone. The phone was not yet configured in the Call Manager and was on Auto Registration. There was enough extension in the pool as well.
The way that I fixed the issue was adding the phone manually into the Call Manager. Then resetting the phone and it started working.
