Check to see that you have the most current software.
Fire & Kindle Software Updates
Also, if this kindle was purchased used, it might have been reported lost or stolen to Amazon. If so, they have blocked registration which would cause the message you are getting.
Kindle Support