Exception using MSDTC Transactions on SQL 2008 / Server 2008 R2 x64 HRESULT: 0x8004D025

I'm currently upgrading an app to SQL 2008 / Server 2008 R2 x64 and I'm seeing some strange behaviour that I have not seen on SQL 2005 / Server 2003. Randomly I get an exception from MSDTC: The partner transaction manager has disabled its support for remote/network transactions. (Exception from HRESULT: 0x8004D025). Please note that I HAVE enabled network transactions without authentication and these transactions do work say 95% of the time. But then some fail with this message. It's a SQLBulkCopy object if that's relevant.

I've investigated the DTC statistics and interestingly when the transaction throws this exception there is no aborted transaction, but it does record one completed transaction. Whats REALLY interesting is that the remote transaction manager ALSO creates a new transaction (status committed). There is a second write as part of the transaction which is successfully written to the database, but the first one is not.

In terms of sequencing, when I see this error the following has occurred:

1. Delete from table (this works)
2. Bulkcopy in new rows (this fails and the exception is raised on the "WriteToServer" method)
3. Create record of the write occuring (this works).

I know that the SQL and the application have both got their MSDTC's configured for remote transactions as several of the transactions do work successfully. Any idea why this is happening and how I could fix it?

Haven't personally seen this one in practice, but found this:

From here:

6. Make sure you check "Network DTC Access", "Allow Remote Client", "Allow Inbound/Outbound", "Enable TIP" (Some option may not be necessary, have a try to get your configuration)
7. The service will restart
8. BUT YOU MAY NEED TO REBOOT YOUR SERVER IF IT STILL DOESN'T WORK