We opened up a microsoft support query, and I got it resolved.
It seems that there can be numerous causes for this error, but in my case,
even though I had DTCPing working bi-directionally, the DTC security settings
were set to use mutual authentication.
This only works if both servers are on the same domain, and ours are in separate DMZ's,
so I went through the following steps on all machines participating
in the distributed transaction to get it working:
1. open up "Component Services"
Control Panel > Administrative tools > Component Services
2. in Component Servies, right click "My Computer" and select "Properties"
Console Root > Component Services > Computers > My Computer
3. select the "MSDTC" tab, and click "Security Configuration" in the "Transaction Configuration" group box
4. in "Security Settings" > "Transaction Manager Communication" select "No Authentication Required"
5. restart the DTC service (should do so automatically)
Originally, I had "Mutual Authentication Required" selected.
I dont know if the "Incoming Caller Authentication Required" option would work.
I hope that this helps some of you!