We have had the same issue and narrowed it down to the installation of security patch KB948111. When we remove the patch, the linked server connection works. We are talking...