Found this thread while searching for the error of my linked server. I know its an old thread but i would like to contribute something people could try when in agony 😛
I used SSMS 2005 for creating the linked server on my SQL2000 instance to my SQL2005 instance on another server. I solved the Access Denied error by NOT chosing SQLNCLI as the provider, maybe this helps others with the same kind of problem.
So...
Linked Server from SQL 2005 -> SQL 2000 use SQLNCLI as provider.
Linked Server from SQL 2000 -> SQL 2005 use Microsoft OLEDB Provider for SQL Server.
Works for me like a charm.