OK, I'm stumped:

I have a client with an SQL 2000 server hosting a database I created for one
of my applications.

The one thing that's odd is this server is not part of the domain, but is
"pingable" from the client computers

When I connect to the database using an ADO connection:

Dim Db as new ADODB.Connection
db.open "driver={SQL Server};server=co_melena;database=MyDatabase",
"MyUsername", "MyPassword"

It will not connect. It claims it cannot find the server, even if I use the
SQL System Administrator login

However, there is a share on this server: \\co_melena\stuff, that I can
open, log into, and close.

After I do this, then running the same code (above) works. Even though the
username and password are completely different for accessing the share, it
somehow "turns something on" that allows me to connect, at least until I
reboot. Now all my privilege levels with the different usernames and
passwords work correctly.

Now, there is another application running with a database on this server
that seems to work fine, and I cannot seem to find a COM or DCOM component
on the server.

So my question is this: Is there a security or role that I have not set?
Is it due to the SQL server not being part of their domain? I would really
appreciate any wisdom you fine folk would share with me.