Starting in PostgreSQL 9.0, it's possible to override the estimates ANALYZE makes for the number of distinct values in a table with your own values, in situations where it's not making a good estimate on its own:
ALTER TABLE t ALTER COLUMN k SET (n_distinct = 500);
In addition to just putting a value in there, you can also set this to a negative value, at which point it's used as a multiplier on the number of rows in the table. That lets you set a distinct estimate that scales along with your data based on current and future expectations about it. There is also a n_distinct_inherited parameter that can be set on a parent that multiple tables inherit from.