This is the error message I'm receiving:
Msg 7391, Level 16, State 2, Procedure spStoredProc, Line 62 [Batch Start Line 1] The operation could not be performed because OLE DB provider "SQLNCLI11" for linked server "MyLinkedServer" was unable to begin a distributed transaction.
As a test my stored procedure query is just
SELECT 1 AS A and works locally on the server but doesn't work when I call it remotely on a linked server.
On the Linked Server properties have you tried setting "Enable Promotion of Distributed Transactions" to False?
You need to have MSDTC (distributed transaction coordinator) running on all the machines involved. See https://stackoverflow.com/questions/7694/how-do-i-enable-msdtc-on-sql-server.