Another 2005 X64 To 2000 X32 Linked Server Problem

Hello,
I have been searching the archives for information on problems that occur with creating a linked server to SQL Server 2000 from SQL Server 2005 x64, but the problem I am having seems to be slightly different.

I was able to create the linked server from the 2005 server this way;

Exec sp_addlinkedserver
@Server = '2kServer',
@srvproduct = 'SQL Server'

I was able to add the login this way;

Exec sp_addlinkedsrvlogin
@rmtsrvname = '2kServer',
@useself='False',
@locallogin='domaincdun2',
@rmtuser='domaincdun2',
@rmtpassword='pswd'

I receive 'Command(s) completed successfully' for both. When I attempt to run either of the following queries from a connection to the 2005 server in Management Studio;

select top 100 * from 2kServer.database.dbo.table
select * from Openquery(2kServer,'select top 10 * from database.dbo.table')

I get the following error

OLE DB provider "SQLNCLI" for linked server "2kServer" returned message "Communication link failure".
Msg 10054, Level 16, State 1, Line 0
TCP Provider: An existing connection was forcibly closed by the remote host.
Msg 18456, Level 14, State 1, Line 0
Login failed for user 'domaincdun2'.

I've seen a couple of ideas on this. One states the following;
***************************************
When running 4 part reference query like this:
select * from sql2000.mybase.dbo.mytable

SQL Server 2005 x64 runs the following query on remote SQL2000 server:
exec [mybase]..sp_tables_info_rowset_64 N'mytable', N'dbo', NULL

Unfortunately there is no such a proc on SQL2k. However, sp_tables_info_rowset exists and does the same thing. The solution is to create wrapper on master database like this:

create procedure sp_tables_info_rowset_64
@table_name sysname,
@table_schema sysname = null,
@table_type nvarchar(255) = null
as
declare @Result int set @Result = 0
exec @Result = sp_tables_info_rowset @table_name, @table_schema, @table_type

And then everything works fine. If you don't want to create "Microsoft like" objects on master database, use openquery instead of 4 part reference.
**************************************
I put this proc on the 2kServer and tried again, but I got the same error. I've also seen this:

I went into the Sql Server Configuration Manager, Sql Native Client
Configuration -> Protocols and disabled Shared Memory and made the TCP/IP
protocol #1 in order. Then just restarted the Sql Service and it all started
working!

I don't have access to the server to do this, but I wonder if it would solve the problem. I am a sys admin on both servers. The servers are in two different domains. Could this be a firewall issue?

Thank you for your help!

cdun2