Yeah, really weird!
I couldn't get it to work with any combination of methods. Update from store, update with apk, uninstall and reinstall from store or with apk, nothing!
And today, as i was going to demonstrate to a friend how the update fails, all of a sudden the installation went through! I had downloaded the apk from AndroidPolice and merely went to install it (which had failed about ten times before!) and it worked!
I have no idea what changed, but I'm happy now. Loving the new UI. Simpler, and the new features rock. Just waiting for all the old ones to be brought back.
Battery drain sucks, tho...