SQL Server Linked Server Permissions
IIRC, try this. I think this is how I fixed it some time ago...

exec sp_configure 'Show Advanced Options', 1; reconfigure;
exec sp_configure 'Ad Hoc Distributed Queries', 1; reconfigure;
go


Edit, attempt 2:

Check this. I've seen this at a previous company (I wasn't sysadmin there) and can't remember what teh DBAs had to do for us to get our linked server to work (also Sybase)

http://blogs.msdn.com/b/dataaccesstechnologies/archive/2010/08/19/permissions-needed-to-set-up-linked-server-with-out-of-process-provider.aspx