Apparently, my phone wasn't the problem, it was AT&T. 3G was down for the area for a lot of people. From what I can discern, there were new servers / network upgrades, and many phones "didn't get the memo", mine being one of them.
An hour or so ago, someone at AT&T hit the "Stop pissing off the customers" button and life returned to it's 100% online 100% of the time goodness.