This may have to do with how AD tokenizes the windows credentials and passes it to the next server. For whatever reason it seems the remote server can not communicate to an AD server to authenticate the user. Have you tried to set the remote server's agent account to use a domain user (Although I don't think this would fix the issue).

I have always used SQL Authentication for linked servers rather than Windows Authentication.