Postgresql not using GIN trigram index when performing non-ASCII LIKE query?
I created your scenario with COLLATE = "C", and both queries use a bitmap index scan index on other_names_lower_trgm_gin as expected.

SQL Fiddle with a table of ~ 10k rows, Postgres 9.2.4, COLLATE = "C".

There is probably something wrong in your setup that is not in your question.
 Run (takes some time for big tables and an exclusive lock!):

VACUUM FULL ANALYZE city;


And try again ...