Solución encontrada por el propio @Dan (no se pudo publicar debido a un representante)
La solución que encontré para este problema fue simplemente agregar la palabra clave "EXEC" a la consulta:
var myEntities = dbContext.Database.SqlQuery<MyEntity>("EXEC GetDataFromMySp @EntityId = {0}", entityId);
Esta solución solucionó el problema con SQL Server 2005 y aún funcionaba con SQL Server 2008 R2.
