You should only be seeing "Android is Upgrading" once, either after a firmware upgrade or you've cleared the Dalvik/VM cache. "Android is Upgrading" during boot means it's actually rebuilding the Dalvik/VM cache, or it's recompiling the all the apps if using ART.
I have seen this once "Android is Upgrading" on every boot. What happened the rebuilding of the Dalvik/VM wasn't completing, although the phone appeared to boot normally. So it was trying to rebuild it every time the phone started, but never completing it. This was on a Lenovo phone. A factory reset fixed it.