You never stated that you actually went through the normal procedure to deregister your Kindle - did you? To get there, use the "Menu > Settings" command, then press the "Registration" (or something to that effect) entry. The Kindle should present you with a dialog box stating something similar to "If you deregister, you won't be able to do this and that. But you can still register again. Are you sure?"
The more radical approach is the "reset to defaults" (or so) entry in the settings menu.
Please post what *exactly* you did.