Cannot fetch the rowset from OLE DB provider "SQLNCLI" for linked server X
No, this is happening because you have a deadlocked resource.  What you need to do is capture the deadlock information with a SQL Trace (you can use SQL Profiler) or with trace flags.

This will give the information (and with a trace, you can get the deadlock graph) to show you what two sessions were having the conflict resulting in the deadlock and a victim to be chosen (which is why you see the error you posted).

Deadlocks happen.  If they are extremely infrequent then it's probably not an issue to worry about.  But if they are happening all the time, then you need to drill down into what query(ies) is(are) causing them.  You may need to rework your DML, or alter your transaction isolation level if it is appropriate (allowing dirty reads is not the answer), or even go with an optimistic isolation level like Snapshot Isolation or Read Committed Snapshot Isolation.  But great consideration needs to be made here, as those optimistic isolation levels utilize row-versioning which will hammer tempdb, so if you don't have an optimial configuration for tempdb you could bring your performance to its knees.