Exactly! Reduce "random_page_cost" down (default is 4) and this becomes a non-issue. It's just one of the less well known things and somewhat difficult to diagnose. What I mean is that what you will see is your database returned rows metric will rapidly climb but rows fetched will hold steady (or decrease). Based on that alone it is a bit of a leap (or at least it was for me at the time) to conclude that the query planner was not using an index on a table that was clearly indexed.
Once you understand what is going on, it makes perfect sense. It's just getting there that is the trick.