Index weirdness - Any ideas why

We are seeing some strangeness with our indexes. Yesterday, one of our
tell tale queries was performing very badly. We tried to analyze the
table, and even vacuum analyze it, but it did not fix the issue.

The issue was general slowness. After we did the maintenance on it, it
would perform very sporadically. Some times it would run sub second,
and then the next run (seconds apart) would run for several seconds.

Has anyone ever seen anything like this?

Here are some explain analyzes to for detail:

explain analyze
select count(1)
from <table>
where hdr_user_id='username'
and hdr_clm_status in ('H','E','A','R','T','V','P','L');

QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=11927.83..11927.83 rows=1 width=0) (actual
time=2191.73..2191.73 rows=1 loops=1)
-> Index Scan using <table>_hdr_user_id_idx on <table>
(cost=0.00..11926.53 rows=521 width=0) (actual time=0.31..2190.98
rows=380 loops=1)
Index Cond: (hdr_user_id = 'username'::character varying)
Filter: ((hdr_clm_status = 'H'::bpchar) OR (hdr_clm_status =
'E'::bpchar) OR (hdr_clm_status = 'A'::bpchar) OR (hdr_clm_status
='R'::bpchar) OR (hdr_clm_status = 'T'::bpchar) OR (hdr_clm_status =
'V'::bpchar) OR (hdr_clm_status = 'P'::bpchar) OR (hdr_clm_status =
'L'::bpchar))
Total runtime:2191.84 msec
(5 rows)

QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=11927.83..11927.83 rows=1 width=0) (actual
time=863.54..863.54 rows=1 loops=1)
-> Index Scan using <table>_hdr_user_id_idx on <table>
(cost=0.00..11926.53 rows=521 width=0) (actual time=0.14..863.22
rows=380 loops=1)
Index Cond: (hdr_user_id = 'username'::character varying)
Filter: ((hdr_clm_status = 'H'::bpchar) OR (hdr_clm_status =
'E'::bpchar) OR (hdr_clm_status = 'A'::bpchar) OR (hdr_clm_status
='R'::bpchar) OR (hdr_clm_status = 'T'::bpchar) OR (hdr_clm_status =
'V'::bpchar) OR (hdr_clm_status = 'P'::bpchar) OR (hdr_clm_status =
'L'::bpchar))
Total runtime: 863.61 msec
(5 rows)

QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Aggregate (cost=11927.83..11927.83 rows=1 width=0) (actual
time=454.50..454.50 rows=1 loops=1)
-> Index Scan using <table>_hdr_user_id_idx on <table>
(cost=0.00..11926.53 rows=521 width=0) (actual time=0.27..453.93
rows=380 loops=1)
Index Cond: (hdr_user_id = 'username'::character varying)
Filter: ((hdr_clm_status = 'H'::bpchar) OR (hdr_clm_status =
'E'::bpchar) OR (hdr_clm_status = 'A'::bpchar) OR (hdr_clm_status
='R'::bpchar) OR (hdr_clm_status = 'T'::bpchar) OR (hdr_clm_status =
'V'::bpchar) OR (hdr_clm_status = 'P'::bpchar) OR (hdr_clm_status =
'L'::bpchar))
Total runtime: 454.60 msec
(5 rows)

Can anyone provide some clues into what is going on here? These queries
were ran within a total of 1 minute elapsed time.

Postgresql 7.3.4 on RedHat 2.1

Thanks for any insite.