Try downloading DTCPing.exe from microsoft and following the recommended solution from there.
Some possible reasons this is failing but not verified.
1. Firewall issues
3. Nested Transactions
4. Remote login permissions.
Can you do a simple select to your linked server? Just want to verify you can at least perform that.
Have you checked your sp_configure advanced options? Ensure that allow updates, remote proc trans, etc are configured properly?
I once got this error because I put begin transaction and commit transaction in a procedure that i called from a linked server. When I removed it and did a direct update I was fine. Even though I know this was not the true solution. I used this work around.
Control Panel -> Admin Tools -> Component Services -> Component Services -> computers -> Right Click My Computer -> Properties -> MSDTC -> "Security Configuration" Check Allow Inbound and Allow Outbound and "No Authentication Required"
Make sure account is "NT AUTHORITY\NetworkService"
Fixed me 99% of the time with servers.
I had to msdtc -uninstall then msdtc -install to re-install to remedy a couple of times. There is an MS Article that outlines the steps, don't know it off the top of my head at the moment.'' Know you said you enabled, but did you click allow inbound and outbound.