By 'enum' I meant in the more general sense, a constrained set of a few values. In our case the original schema designer used a text column for states: 'active,' 'dead,' etc. The planner would generally guess incorrectly about the range of values it might expect to find in a text column like that and working around it required hand fiddling.
(Disclaimer: forgive me, it's been a few years since I've had to deal with this specific problem, some of the details may be off.)
Was it indexing the faux-enum columns? First thing I would do would be to drop the index if there is one considering it will add very little to the selectivity of the query.
(Disclaimer: forgive me, it's been a few years since I've had to deal with this specific problem, some of the details may be off.)