Try dropping and recreating the user id on both servers. Finally worked for me after pulling my hair out for 2 hours. Orginally the problem was caused when I scripted and executed drop and create of the linked server. Can't explain as the user id and password were the same as always on both servers, but it worked.:-D