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.
