May be you have very bad disk access times (e.g. slow random access)? In this case everything should be OK while data in cache and awful, when not. Could you check disk IO speed && IO wait while doing slow & fast query.
BTW: In this case, increasing shared buffers may help. At least this will prevent other applications & AFAIK sequence scans to move your index data from cache.