Dropped an index and recreated it in PostgreSQL 9.2, not used anymore
I solved the mystery on pg irc channel - I had a long running query (idle in transaction) and they told me that a new index doesn't get used until all transactions that started before its creation don't finish.

Killed the transaction, and now the indexes are back to normal.