You didn't install/update to a newer version of the Android Kindle app from another source, did you? The Kindle Fire version of the Kindle app is tightly integrated into the Fire's environment. The standalone Android Kindle app is a different beast altogether.
I'd definitely try de-registering/re-registering first. Then escalate to a factory reset if that doesn't work. Unless you've done some pretty serious hacking, I'd expect the reset to restore functionality. I personally wouldn't get Amazon involved until I exhausted those options. They're going to walk you through doing one, or the other, or both of those things anyway.
