Optimize slow query

Hi,
I've a table with 300 000 records and I'm trying to do a search:

SELECT * FROM addresses WHERE address ILIKE '%Jean Paul%' AND
(l_pc='4250' or r_pc='4250') AND (l_struc='O' or r_struc='O') AND
(prenm ILIKE 'Street')

It performs in 2 seconds in a dual Xeon 2.4mhz with 2Gb of RAM.
I'm using Postgresql 8.1 on ubuntu.
I've indexes on l_pc, r_pc, l_struc,r_struc and prenm (all btrees)
What I'm doing wrong to have such a slow query?

Thanks,
Nuno Mariz