I think SQL Server 2000 Service Pack 4 may exist in your machine.

Problem may be ODBC Drivers or TCP/IP ports.

Run the following commands if server is offline:

DBCC UPDATEUSAGE ([DBNAME])

DBCC CHECKDB

DBCC DROPCLEANBUFFERS

sp_spaceused.

for more information, see the DBCC related command in SQL BOL.

check the below links, it may solve your problem:

http://www.alagad.com/go/blog-entry/one-solution-to-this-error-sql-server-does-not-exist-or-access-denied

http://blogs.msdn.com/sql_protocols/archive/2005/12/19/505372.aspx

http://www.experts-exchange.com/Programming/Programming_Languages/Dot_Net/Q_20789603.html

http://support.microsoft.com/kb/314530