3/26/2014 - Since writing this question, a patch has been released.
It can be found here: http://support.esri.com/en/downloads/patches-servicepacks/view/productid/160/metaid/2003
The bing basemap seems to have been recently removed from the "Add Basemap" dialogue in ArcMap. I'm using 10.1. I've also heard reports from a coworker that a bing basemap layer was replaced by the dreaded red exclamation mark in an existing document she was using.
Any idea if bing/ esri altered their relationship, or is this just a local problem on my end?