Unable to use index?

Hi folks!

A query I am running does not seem to use indexes that are available
(running version 7.4.2). I have the following table:

=> \d replicated
                                    Table "public.replicated"
     Column      |           Type           |
Modifiers
-----------------+--------------------------+-----------------------------------------------------
 rep_id          | bigint                   | not null default nextval('replicated_id_seq'::text)
 rep_component   | character varying(100)   |
 rep_key1        | integer                  |
 rep_key2        | bigint                   |
 rep_key3        | smallint                 |
 rep_replicated  | timestamp with time zone |
 rep_remotekey1  | integer                  |
 rep_remotekey2  | bigint                   |
 rep_remotekey3  | smallint                 |
 rep_key2b       | bigint                   |
 rep_remotekey2b | bigint                   |
 rep_key4        | text                     |
Indexes:
    "replicated_pkey" primary key, btree (rep_id)
    "replicate_key1_idx" btree (rep_key1, rep_key2, rep_key3)
    "replicated_item2_idx" btree (rep_component, rep_key2, rep_key3)
    "replicated_item_idx" btree (rep_component, rep_key1, rep_key2, rep_key3)
    "replicated_key2_idx" btree (rep_key2, rep_key3)
    "replicated_key4_idx" btree (rep_key4)

=> analyze verbose replicated;
INFO:  analyzing "public.replicated"
INFO:  "replicated": 362140 pages, 30000 rows sampled, 45953418 estimated
total rows
ANALYZE

The following does not use an index, even though two are available for the
specific selection of rep_component.

=> explain analyze select * from replicated where rep_component = 'ps_probe' limit 1;
                                                          QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.23 rows=1 width=101) (actual time=34401.857..34401.859 rows=1 loops=1)
   ->  Seq Scan on replicated  (cost=0.00..936557.70 rows=4114363 width=101) (actual time=34401.849..34401.849 rows=1
loops=1)
         Filter: ((rep_component)::text = 'ps_probe'::text)
 Total runtime: 34401.925 ms
(4 rows)

Yet, if I do the following, an index will be used, and it runs much
faster (even when I swapped the order of the execution).

=> explain analyze select * from replicated where rep_component = 'ps_probe' order by rep_component limit 1;
                                                          QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..1.66 rows=1 width=101) (actual time=51.163..51.165 rows=1 loops=1)
   ->  Index Scan using replicated_item2_idx on replicated  (cost=0.00..6838123.76 rows=4114363 width=101) (actual
time=51.157..51.157rows=1 loops=1) 
         Index Cond: ((rep_component)::text = 'ps_probe'::text)
 Total runtime: 51.265 ms
(4 rows)

Any reason why the index is not chosen? Maybe I need to up the number of
rows sampled for statistics?

Regards!
Ed