The complete message you receive for the subject transaction is:

Server: Msg 7391, Level 16, State 1, Line 2
The operation could not be performed because the OLE DB provider 'SQLOLEDB' was unable to begin a distributed transaction. OLE/DB provider returned message: New transaction cannot enlist in the specified transaction coordinator.

This error occurs because, by default, the Microsoft Distributed Transaction Coordinator (MS DTC) is not configured for network access on new installations of SQL Server 2000 on Windows Server 2003, Enterprise Edition.

To configure MS DTC for network access:

01. Open Component Services from the Administrative Tools folder.

02. In the Component Services Wizard, expand Component Services and double-click Computers.

03. Right-click My Computer and press Properties.

04. Select the MS DTC tab.

05. Press Security Configuration.

06. In the Security Configuration dialog, select the Network DTC Access box.

07. Under Network DTC Access, press Network Transactions.

08. Insure that the DTC Logon Account is set to NT Authority\NetworkService.

09. Press OK.

10. Press Yes to continue.

11. Press OK in the DTC Console Message dialog.

12. Press OK in the System Properties dialog.

NOTE: See HOWTO: Troubleshoot MS DTC Firewall Issues.