Can you connect to the linked server using the userid and password.

i hope that is password issue.