I had the exact same problem. Monitoring web traffic showed that it was attempting to connect to serverapi.arcgisonline.com/veadaptor, and receiving an authentication error from that as well. Pasting the JSON created by the PrintTask into the rest endpoint fails, i.e.
"operationalLayers":[
{
"opacity":1,
"visibility":true,
"type":"BingMapsRoad",
},
However, if you modify this and include your Bing key
"operationalLayers":[
{
"opacity":1,
"visibility":true,
"type":"BingMapsRoad",
"key":"<insert key here>"
},
it works fine and the map is exported correctly. I talked to ESRI support and they said that Bing authentication procedures is changing rather quickly. Unfortunately, right now the JSON created by the PrintTask doesn't include the key. They logged it as a bug [#NIM091676 Bing layer JSON needs to include key and made it sound like this is a pretty time-sensitive fix and that it should be included in the next release.