Unable to begin a distributed transaction

Found it, MSDTC on the remote server was a clone of the local server.

From the Windows Application Events Log:

Event Type: Error
Event Source: MSDTC
Event Category: CM
Event ID: 4101
Date: 9/19/2011
Time: 1:32:59 PM
User: N/A
Computer: ASITESTSERVER
Description:

The local MS DTC detected that the MS DTC on ASICMSTEST has the same unique identity as the local MS DTC. This means that the two MS DTC will not be able to communicate with each other. This problem typically occurs if one of the systems were cloned using unsupported cloning tools. MS DTC requires that the systems be cloned using supported cloning tools such as SYSPREP. Running 'msdtc -uninstall' and then 'msdtc -install' from the command prompt will fix the problem. Note: Running 'msdtc -uninstall' will result in the system losing all MS DTC configuration information.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.

Running

msdtc -uninstall
msdtc -install

and then stopping and restarting SQL Server service fixed it.

I was able to resolve this issue (as others mentioned in comments) by disabling "Enable Promotion of Distributed Transactions for RPC" (i.e. setting it to False):

As requested by @WonderWorker, you can do this via SQL script:

EXEC master.dbo.sp_serveroption
     @server = N'[mylinkedserver]',
     @optname = N'remote proc transaction promotion',
     @optvalue = N'false'