Query and index ... unexpected result need advice.

Hello,
Yesterday when I read the email I came across an issue and I thought 
very interesting result. The topic is: "Table with million rows - and 
PostgreSQL 9.1 is not using the index". I decided to try it because from 
250 ms with millions rows to 15 ms is very good, but I did not get the 
expected result, rather worse. I am interested to know where is my 
mistake or something wrong with server which I doubt. Here is my current 
query with explain:
(I change names to XXX YYY ZZZ because original names is written on 
CP1251 and most ppl in list can't read them)

db=# explain analyze SELECT *,COALESCE(firstname,'') || ' ' || 
COALESCE(middlename,'') || ' ' || COALESCE(lastname, '') AS name FROM 
clients_tbl WHERE firstname = 'XXX' AND middlename || lastname LIKE 
'%YYY%ZZZ%';
                                                                QUERY 
PLAN
----------------------------------------------------------------------------------------------------------------------------------------
  Bitmap Heap Scan on clients_tbl  (cost=230.90..32648.50 rows=1 
width=602) (actual time=12.649..35.919 rows=1 loops=1)
    Recheck Cond: (firstname = 'XXX'::text)
    Filter: ((middlename || lastname) ~~ '%YYY%ZZZ%'::text)
    Rows Removed by Filter: 11727
    ->  Bitmap Index Scan on clients_tbl_firstname_idx  
(cost=0.00..230.90 rows=11886 width=0) (actual time=5.415..5.415 
rows=11728 loops=1)
          Index Cond: (firstname = 'XXX'::text)
  Total runtime: 35.988 ms
(7 rows)

35 ms isn't bad, but it's will be good if I can optimize it more.
firstname, middlename, lastname is declarated as TEXT;

create index clients_tbl_firstname_idx on clients_tbl using btree 
(firstname);
create index clients_tbl_middlename_idx on clients_tbl using btree 
(middlename);
create index clients_tbl_lastname_idx on clients_tbl using btree 
(lastname);

I dropped both indexes and create new one:

create index clients_tbl_firstname_idx on clients_tbl using btree 
(firstname COLLATE "bg_BG" text_pattern_ops);
create index clients_tbl_middlename_idx on clients_tbl using btree 
(middlename COLLATE "bg_BG" text_pattern_ops);
create index clients_tbl_lastname_idx on clients_tbl using btree 
(lastname COLLATE "bg_BG" text_pattern_ops);

My server is in CP1251 encoding:

                                                                      
List of databases
     Name    |  Owner   | Encoding |   Collate    |    Ctype     |   
Access privileges   |  Size   | Tablespace |                Description
------------+----------+----------+--------------+--------------+-----------------------+---------+------------+--------------------------------------------
   db        | postgres | WIN1251  | bg_BG.CP1251 | bg_BG.CP1251 | 
=Tc/postgres         +| 121 GB  | pg_default |

I run the same query again:

db=# explain analyze SELECT *,COALESCE(firstname,'') || ' ' || 
COALESCE(middlename,'') || ' ' || COALESCE(lastname, '') AS name FROM 
clients_tbl WHERE firstname = 'XXX' AND middlename || lastname LIKE 
'%YYY%ZZZ%';
                                                   QUERY PLAN
---------------------------------------------------------------------------------------------------------------
  Seq Scan on clients_tbl  (cost=0.00..105444.47 rows=1 width=602) 
(actual time=56.343..381.068 rows=1 loops=1)
    Filter: ((firstname = 'XXX'::text) AND ((middlename || lastname) ~~ 
'%YYY%ZZZ%'::text))
    Rows Removed by Filter: 1279568
  Total runtime: 381.137 ms
(4 rows)

381 ms ...

Any one have ides ?

Thanks,
H.S.