If this counts for anything or amazes anyone. I ran the OTA using Clockwork Mod. LOL I thought you couldn't do OTAs through CWM?!! WTFBBQ?! Was there a change? I remember CWM from my G1 and Gtab and that was the norm.
Anywho, I also spoke to Samsung people right now about that message and boy were they helpful /sarcasm
They told me that I wasn't supposed to receive any updates, that.. get this, it must have been a Google Play app update instead. LMAO, like I would confuse that over a "New Software Update is Available" message.
To the guy who asked about the OTA root survival. Its built into Superuser. You can also try OTA Root Survival.
EDIT: Looks like I lost CWM, just rebooted into Clockwork Mod using Rom Manager and it booted me into what looks like stock recovery. Phone stuck on the Andy with spinning Zune logo. Hope this doesn't brick my phone.