Hi. This is a bit of an old thread, but this error happened to me today. And I confirmed that it is caused by missing the select permission on the second side of the linked-server. If you map every login used on the linked-server this can be avoided, but if you use Windows Authentication or "map the corresponding login" you may end up passing a login without the correct permissions and not notice it. Just give the permission and the error will go away.
It is not the most user-friendly message, but as it seems the linked-server feature needs to schema_lock every object on select...
I made a post about this issue: http://thelonelydba.wordpress.com/2013/04/17/sql-and-linked-servers-the-schema-lock-permission-was-denied-on-the-object/