It sounds to me like two possible problems, maybe combined.
One possibility is that you have a data distribution that results in
statistics being gathered that don't really represent your data. Try
increasing the stats target for that column (or the whole db if you'd
rather) and re-running analyze.
The other possibility is that you've got some index bloat happening
and you might benefit from reindexing the problematic table.