> My problem is not that PostgreSQL does not understand the distribution of my data. It does. The problem is that it comes up with a query plan without realizing that I'm only querying for a very small range of timestamps.

Which version did you reproduce that on? While the problem has not been generally addressed, the specifically bad case of looking up values at the "growing" end of a monotonically increasing data range has been improved a bit over the years (9.0 and then some incremental improvement in 9.0.4).