> There are other tables, such as the messages table, that have 10s of
> thousands of rows and they return records much more quickly.
> There must be something seriously wrong for simple queries like this to take
> so long.
Have you run VACUUM recently?
If not, run VACUUM FULL against the users table and see if that makes a
difference.