If you are running Windows 2003 SP1 and non-Windows 2003 SP1, check out your DTC authentication level.  SP1 allows the ability to control both inbound and outbound authentication. 

If the linked servers...