I was gettin this error  when i try to execute a stored procedure from linked server.

Executed as user: XXX\yyy. The OLE DB provider "SQLNCLI"
for linked server "LSQL02" reported an error.
Authentication failed. [SQLSTATE 42000] (Error 7399)  Cannot initialize the data source object of OLE DB provider "SQLNCLI" for linked server "LSQL02". [SQLSTATE 42000] (Error 7303)  OLE DB provider "SQLNCLI" for linked server "LSQL02" returned message "Invalid authorization specification". [SQLSTATE 01000] (Error 7412).  The step failed.

To solve you can map Servers local user to remote servers user with executing 'sp_addlinkedsrvlogin'

EXEC sp_addlinkedsrvlogin @rmtsrvname = 'linkedservername'

      , @useself = 'FALSE'

      , @locallogin = 'localuser'

      , @rmtuser = 'remoteuser'

      , @rmtpassword = 'remoteuserpassword'

EXEC sp_droplinkedsrvlogin @rmtsrvname = 'linkedservername'

      ,@locallogin = 'localuser'

References

Security for Linked Servers
http://msdn.microsoft.com/en-us/library/ms175537.aspx

sp_addlinkedsrvlogin (Transact-SQL)
http://msdn.microsoft.com/en-us/library/ms189811.aspx

sp_droplinkedsrvlogin (Transact-SQL)
http://msdn.microsoft.com/en-us/library/ms186218.aspx