OK... so an update...
After spending an hour and 15 minutes on the phone with Verizon Customer Service, it seems like the problems I had above are all resolved, or at the very least, they have been addressed.
Data connectivity was restored to working condition after the rep reset the network on their end. Have a very solid and strong 3G signal now that does not drop (at least not so far). As for the software update, apparently HTC has not released the update to all devices, and are staggering to whom the update will go. Seems to be focusing on the 4G markets first, and then moving to the 3G markets. The update is rolling out based on area codes (or at least thats what I've been told, and it makes sense to me since I use an out of market area code). If your phone checks for the update and does not come back with any kind of result (i.e. the popup just closes) thats a good sign, as it means that it recognizes the update is there, but HTC has not authorized that area for download, yet.
However, somehow through a series of factory resets and battery pulls, the Market has been... well... its just not working. Every download goes straight to FAIL. Ugh, so I'm currently working on that and will hopefully have that resolved soon. Other than that, its running much better than it was before. Have to say, one of my better Customer Service experiences in a while. I think those Tech guys are more willing to help when they realize you know what you're talking about.