indices - used by which user ?

I have two tables (2000-4000 entries each) owned by the postgres
superuser and built an index on one of them. If I connect to the
database as user postgres and do a natural inner join on the two tables
(the index coloumn) the index is used and my query executes at about 80
ms (verified with explain analyze). If I connect as another user (for
whom access to the two tables is also granted) and do the same query,
the index is not used and the query takes ~ 800 ms. Both cases are under
psql. Additionally, after   issuing a \c - <same other user> when
connected as the not postgres user, the index will be used (very strange).
I searched the docs, but found no kind of grant, that works on indices.
Are there any access priveledges on indices or am I missing some other
point ? Ah, nearly forgot - Version 7.3.1

Gerhard