Just had another problem with link server, but managed to successfully decide it.
Will describe it here, may be it'll help somebody.
In the SQL server there is a view, that uses data from the linked server. Then in the stored procedure we use this view for updating some information in the database. The update statement tries to change data in the linked table. This update statement was producing an error. Instead of update statement I've just created a cursor and made changes in the cycle and this works.