A first remark : SQL Server 2000 is no longer supported ( even in extended support ).The same thing is occurring shortly for SQL Server 2005 ( all SP ). It would be useful to upgrade your SQL Server towards SQL Server 2008 R2 ( the direct jump to SQL Server 2012 is impossible ).
Usually , when I have a problem of connection to a SQL Server , I am searching the answer in the SQL Server Protocols Blog
http://blogs.msdn.com/b/sql_protocols/ where I find quickly a solution to my problem.
But you are using SQL Server 2000 and I have noticed a little sentence which could make more difficult to find the solution
"One of the more visible changes we made in connectivity space for SQL Server 2005 was enhancing error messages reported to the user in case of connection failures"
- SQL Browser is not existing before SQL Server 2005 which makes less easy the remote connections
see http://blogs.msdn.com/b/sql_protocols/archive/2005/09/22/473111.aspx and
Some useful links :
Even if these articles were written for SQL Server 2005 and over , some ideas they provided could be useful for you
A last thing : which is the last service pack installed on your SQL Server ? Which is the edition also ?
Have a nice day