We had similar issues(same error) a few jobs ago when upgrading the OS and SQL same day. Maybe you did, or didnt also upgrade the OS, but our problem was the DTC co-ordinator. We dug and dug blaming sql until finally found an error with enough info to reveal MSDTC was the problem.

We added both machine names and tweaked DTC on both servers, doing nothing to sql at all, if it's enabled already maybe you need other changes. Each jump in versions has impending consequences and I've learned never discount cause something worked version to version especially in this case, being way apart.