I've been having the same thing as the OP. I get "Android is Upgrading" when it restarts, too.
In additiona I've seen (several times now) that when I press the power button to turn the screen on, it wont accept any input. After 30 minutes or so it spontaneously restarts and goes to the "Android is Upgrading" message when it restarts.
I'm on the verge of RMI'ing the thing as some of the other guys in the office who have it have not had the same problems.
I'm running vanilla sim free version, no operator tat installed.