The MSDTC transaction manager was unable to push the transaction to the destination transaction manager due to communication problems

I have a BizTalk server and a SQL server which BizTalk sends messages via WCF-SQL to. The BizTalk server has been calling to this server for over a year with no problems. I came in this morning any suddenly it can't (it was working on Friday).

The full error I'm getting when calling the WCF-SQL endpoint is:

A message sent to adapter "WCF-SQL" on send port "MyPort" with URI "mssql://mySQLServer" is suspended.
Error details: System.Transactions.TransactionManagerCommunicationException: Communication with the underlying transaction manager has failed. ---> System.Runtime.InteropServices.COMException:
The MSDTC transaction manager was unable to push the transaction to the destination transaction manager due to communication problems.
Possible causes are: a firewall is present and it doesn't have an exception for the MSDTC process, the two machines cannot find each other by their NetBIOS names, or the support for network transactions is not enabled for one of the two transaction managers. (Exception from HRESULT: 0x8004D02A)
at System.Transactions.Oletx.ITransactionShim.Export(UInt32 whereaboutsSize, Byte[] whereabouts, Int32& cookieIndex, UInt32& cookieSize, CoTaskMemHandle& cookieBuffer)
at System.Transactions.TransactionInterop.GetExportCookie(Transaction transaction, Byte[] whereabouts)

I've followed instructions from the following thread: MSDTC on server 'server is unavailable

I've run msdtc -uninstall then msdtc -install and restarted the service several times.

I've rebooted the server several times.

I can connect to the database using Sql Server Management Studio

DTCPing when trying to connect from the SQL server to the Biztalk server results in (when DTCPing is running on the BizTalk):

Problem:fail to invoke remote RPC method
Error(0x6BA) at dtcping.cpp @303
-->RPC pinging exception
-->1722(The RPC server is unavailable.)
RPC test failed

when going from Biztalk to SQL I get this (even thought DTCPing is running on the other end)

Please refer to following log file for details:
C:\Temp\DTCPing\myserv.log
Invoking RPC method on dbaditest
RPC test is successful
++++++++++++RPC test completed+++++++++++++++
Please start PING from dbaditest to complete the test

neither server is running a firewall at all

I'm all out of things to try.

Edit: I can confirm that other servers/computers can connect to the SQL server. So I have to assume that it's the BizTalk server that is the problem.

Edit 2: I tried connecting from BizTalk Server to another SQL server on the network and got the same error. I'm moments away from throwing my hands up and rebuilding my dev environment -- ugg :(

Edit 3: I can telnet to port 135 from BizTalk to SQL Server, so there's nothing blocking it.

Edit 4: DTCTester results in:

tablename= #dtc24449
Creating Temp Table for Testing: #dtc24449
Warning: No Columns in Result Set From Executing: 'create table #dtc24449    (ival int)'
Initializing DTC
Beginning DTC Transaction
Enlisting Connection in Transaction
Error:
SQLSTATE=25S12,Native error=-2147168242,msg='[Microsoft][ODBC SQL Server Driver]Distributed transaction error'
Error:
SQLSTATE=24000,Native error=0,msg=[Microsoft][ODBC SQL Server Driver]Invalid cursor state
Typical Errors in DTC Output When
a.  Firewall Has Ports Closed
-OR-
b.  Bad WINS/DNS entries
-OR-
c.  Misconfigured network 
-OR-
d.  Misconfigured SQL Server machine that has multiple netcards.
Aborting DTC Transaction
Releasing DTC Interface Pointers
Successfully Released pTransaction Pointer.

You've already taken some steps here, but carefully go through the MSDN Article on Troubleshooting MSDTC.

I'd be concerned that someone imaged another server off of yours, but uninstalling and reinstalling MSDTC should have fixed that. It might be worth checking on these registry values as well (from the above link):

Windows enhances security by requiring authenticated calls to the RPC interface. This functionality is configurable through the EnableAuthEpResolution and RestrictRemoteClients registry keys. To ensure that remote computers are able to access the RPC interface, follow these steps:

Click Start, click Run, type regedit.exe, and then click OK to start Registry Editor.

Navigate to HKEY_LOCAL_MACHINE\SOFTWARE\Policies\Microsoft\Windows NT

Under the RPC key, create the following DWORD entries with the indicated values. If the RPC key does not exist then it must be created.

DWORD entry             Default value  Recommended value
EnableAuthEpResolution  0 (disabled)   1
RestrictRemoteClients   1 (enabled)    0

Close Registry Editor.

Restart the MSDTC Service.