Linked Server Error in SQL Server 2005

Hi,
I have set up a linked server and on both the servers I have set up mixed mode authentication, still when i try to query the linked server I am getting the following error.

Msg 18456, Level 14, State 1, Line 1
Login failed for user ‘sa’.

I don’t know why?

Also I would like to know whether both the servers should be on same domain in order for the linked server to work?
Is there any thing I am missing here??

Any help would be appreciated.