Contact the one who gave you the gift. Amazon registered my kindle to my account right at the day of shipment and even informed me about this via email. The kindle itself was never used so it appeared as not registered after power on. The one who bought it certainly have it registered to his account and you have to either use his email and password on your kindle or ask him/her to deregister it from amazon account.
In any other case just write an email to kindle-support.