I have the Kindle is upgrading message also. It takes almost one minute for my Kindle HDX 7 in to load up. What I found that helped this was not to use Gapps. What I did is on the stock rom I used a suggestion from another forum member on installing GAPPs at http://forum.xda-developers.com/show...577826&page=17
On the Rom slot-1, I used Gapps Zip to see if I was correct in my theory and I was. I don't get it on my stock rom because I installed the Google PlayStore differently using this member's suggestion: http://forum.xda-developers.com/show...577826&page=28
Post 271. What's interesting is that the Amazon ads returned only when the Kindle goes into hibernation.
However, in not installing the Gapps Zip you give up wallpapers. I can't get wallpapers to work on my stock rom since I didn't use the Gapps Zip. Wallpapers do work on my Rom Slot 1 where the Gapps Zip is installed. I get the Kindle is upgrading message and Amazon ads are back when the Kindle goes into hibernation, not on reboot.
So, I just deal with it. I'm glad to have the Playstore and the other little issues I just try not to let it bother me.