The problem of new indexes messing up otherwise good queries is something I've battled on and off for the past decade with Postgres. Definitely annoying.
I definitely have seen the query planing make some peculiar choices in the past.
I think the main index type that bit me are the ones created by exclusion constraints. Often times it looks to the planner like "the right" index to use, but there is another (btree) that is way cheaper...the exclusion constraint is just there to ensure consistency.
In those cases to fix things, I added a WHERE clause to the index (e.g. WHERE 1=1), and the planner wouldn't consider that index unless it saw that same 1=1 condition in the queries WHERE clause.