You're right re: the security. 

On the slightly obscur side, when creating the connection (linked server) are/were there two different drivers for AS? (prob listed as OLE DB for OLAP 8.0 and 9.0).  I know with Excel connections, if you use the 'old" (sql server 7.0/OLAP services) driver, you can't connect to catalogs that contain AS2000 features.  It may be that when connecting via TS, the TS machine has only the latest driver but your client PC/s have both?