This may be due to some patch made on one of the servers.

Can you test with openquery to see there is no permission, configuration issues

Select * from openquery(linkservername,'select top 1 * from dbname.schemaname.yourtablename')

I had faced similar issues when creating linked server from 64 bit

http://support.microsoft.com/default.aspx?scid=kb;en-us;906954#appliesto%5B/url%5D