select count(*) performance (vacuum did not help)

hi,

i have the following table:

CREATE TABLE "main_activity" (
     "id" serial NOT NULL PRIMARY KEY,
     "user_id" integer NOT NULL,
     "sessionid" varchar(128) NOT NULL,
     "login" timestamp with time zone NOT NULL,
     "activity" timestamp with time zone NOT NULL,
     "logout" timestamp with time zone NULL
)

the problem is that it contains around 20000 entries,  and a select
count(*) takes around 2 minutes. that's too slow.

some background info:

- this table has a lot of updates and inserts, it works very similarly
to a session-table for a web-application

- there is a cron-job that deletes all the old entries, so it's size is
rougly between 15000 and 35000 entries (it's run daily, and every day
deletes around 10000 entries)

- but in the past, the cron-job was not in place, so the table's size
grew to around 800000 entries (in around 80 days)

- then we removed the old entries, added the cronjob, vacuumed +
analyzed the table, and the count(*) is still slow

- the output of the vacuum+analyze is:

INFO:  vacuuming "public.main_activity"
INFO:  index "main_activity_pkey" now contains 11675 row versions in
57301 pages
DETAIL:  41001 index row versions were removed.
56521 index pages have been deleted, 20000 are currently reusable.
CPU 1.03s/0.27u sec elapsed 56.08 sec.
INFO:  index "main_activity_user_id" now contains 11679 row versions in
41017 pages
DETAIL:  41001 index row versions were removed.
37736 index pages have been deleted, 20000 are currently reusable.
CPU 0.70s/0.42u sec elapsed 62.04 sec.
INFO:  "main_activity": removed 41001 row versions in 4310 pages
DETAIL:  CPU 0.15s/0.37u sec elapsed 20.48 sec.
INFO:  "main_activity": found 41001 removable, 11672 nonremovable row
versions in 160888 pages
DETAIL:  0 dead row versions cannot be removed yet.
There were 14029978 unused item pointers.
0 pages are entirely empty.
CPU 5.53s/1.71u sec elapsed 227.35 sec.
INFO:  analyzing "public.main_activity"
INFO:  "main_activity": 160888 pages, 4500 rows sampled, 4594 estimated
total rows

(please note that the "4594 estimated total rows"... the row-count
should be around 15000)

- this is on postgresql 7.4.8 .yes, i know it's too old, and currently
we are preparing a migration to postgres8.1 (or 8.2, i'm not sure yet),
but for now i have to solve the problem on this database

thanks a lot,

gabor