PostgreSQL not using varchar index when ordering by primary key
PostgreSQL thinks that it can avoid the expensive sort by using an index that returns the rows in sorted order and filter out the rows that do not match the conditions. This strategy turns out to be bad, either because of mis-estimates or an adversarial distribution.

Sorting by primary key is in no way faster than sorting by other indexed criteria. And in this case you are better off not having an index on the ORDER BY expression.

You should at least upgrade to the latest 9.4 bugfix release, but better to a recent version, because it is dangerous to use old and unsupported versions. They can contain bugs that may eat your data. Just because no such bug has manifested so far is no guarantee that it won't in the future.