SQL Server 2008 R2 - Access Failure in a query that uses Linked server
A number of comments asked if Kerberos was configured correctly, but I do not see a direct response to that issue.  Based on the comments that you make I suspect Kerberos is not set up correctly. 

Greatly simplified description:


If UserAccount is directly logged onto Server A then a linked server to Server B is one hop away and the UserAccount's authentication will be recognized on Server B.  This works with or without Kerberos delegation.
Is UserAccount is directly logged onto his desktop and accesses Server A then Server A is one hop away from the desktop and the UserAccount's authentication will be recognized on Server A. However, if from the desktop he runs a query against Server A that uses a linked server to access Server B that is two hops away from his desktop. Without Kerberos (or some similar service) the UserAccount's delegation cannot make the second hop and, despite the rights granted on Server B, will not authenticate on Server B.


This is all about how NTLM and Kerberos work. There is a blog from a few years ago that offers some details on Linked Servers and NTLM or Kerberos authentication: 

http://blogs.msdn.com/b/sql_protocols/archive/2006/08/10/694657.aspx

One edited quote is: "In a single-hop setting, windows NTLM authentication, which is available if all machines are windows, is sufficient for delegation; while in a double-hop setting, Kerberos authentication is necessary for the user’s credential to cross machine boundaries from the client to the linked server."

Now, suppose that you do indeed have Kerberos configured properly and still are mystified by the behavior.  In that case you might need to check into whether there is a duplicate SPN.  If so that will need to be corrected.

The following blog discusses duplicate SPNs and other Kerberos issues:
http://blogs.technet.com/b/askds/archive/2013/07/01/interesting-findings-on-setspn-x-f.aspx

Note: Some people just fall back to using Named Pipes instead of TCP/IP, but this is not a recommended solution any more. 

Bottom line: Resolve the authentication delegation problem and everything should work.