Same here. Retrying the job doesn't help.
I digged a bit more by mixing the different types of operations and I found that creating a batch job with with these two operations always makes the batchjob fail (in my particular case):
{u'AdGroupCriterionOperation':
[{u'operator': u'SET',
u'operand': {u'biddingStrategyConfiguration': {
u'bids': [{u'bid': {u'microAmount': '1200000'}, u'xsi_type': u'CpcBid'}]},
u'adGroupId': u'21329742443', u'criterion': {u'id': u'188722430705'},
u'xsi_type': u'BiddableAdGroupCriterion'},
u'xsi_type': u'AdGroupCriterionOperation'}],
u'AdGroupCriterionLabelOperation':
[{u'operator': u'REMOVE',
u'operand': {u'adGroupId': u'11205179483', u'criterionId': u'70136100181',
u'labelId': 42329003, u'xsi_type': u'AdGroupCriterionLabel'},
u'xsi_type': u'AdGroupCriterionLabelOperation'}]
}
Hope this helps you debugging it.