I have the same problem as Greg. I am trying to connect to a remote SQL Server 2000 DB from SQL Server 2005 Management Studio and I get the exact same error message. Any ideas??
I can connect using Enterprise Manager so the remote server is fine.