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.