What was set on the security settings for the linked server properties? Some have suggested enabling the "Be made using this security context" option and putting in the other server's sa login information.