You get this type of error when you have specified a trusted connection (Windows) and the username/password in the connection string. My guess is you have specified the username and password because the connection is coming from a different domain - which isn't necessary.
You are correct, Jeff. The connection originates from a diff domain.
The connection gets TO the instance but fails here:
Cannot open database "My_Database" requested by the login. The login failed.
Login failed for user 'MyDomain\MyLogin'. I even grant the login sysadmin to rule out any permissions issues, still get this error.
What does the connection string look like? If you are trying to use a trusted connection - then you cannot specify the username/password and the from domain needs to be trusted.