SQL linked server returning error suddenly upon query
This does look like a network issue, as per this question on MSDN the "Protocol error in TDS stream" indicates as such.

This seems to be a very similar question that was resolved by disabling TCP Chimney Offload (think link in that question directs to a veritas article that describes how to do it).

Which may be a quick (and possibly dirty) was of trying to resolve it. If that is not the problem, then it is almost certainly a network problem (maybe a nic problem). 

--

Edit:

Might be worth making sure the native client is fully up to date (by updating SQL Server, which is no bad thing anyway).

Also, if you're still struggling, add some more information about your environment to your question e.g. OS version, SQL Server version &amp; update level, information about your nics etc.