Optimizing queries on a range of timestamps (one column)
Two things that are very odd here:


The query select 300k rows from a table with 1M+ rows. For 30 % (or anything over 5 % - depends on row size and other factors) it doesn't typically pay to use an index at all. We should see a sequential scan.

The exception would be index-only scans, which I don't see here. The multicolumn index @Craig suggested would be the best option if you get index-only scans out of it. With lots of updates like you mentioned, this may not work out, in which case you are better off without the additional columns - and just the index you already have. You might be able to make it work for you with more aggressive autovacuum settings for the table. You can adjust parameters for individual tables.
While Postgres is going to use the index I would certainly expect to see a bitmap index scan for that many rows, not a plain index scan, which is typically the better choice for a low percentage of rows. As soon as Postgres expects multiple hits per data page (judging from its statistics on the table) it will typically switch to a bitmap index scan.


Keep PostgreSQL from sometimes choosing a bad query plan



Judging from that I would suspect that your cost settings are inadequate (and possibly the table statistics, too). You  may have set random_page_cost and / or cpu_index_tuple_cost too low, relative to seq_page_cost. Follow the links and read the manual.

Would also fit with the observation that cold cache is large factor, as we worked out in comments. Either you are accessing (parts of) tables that nobody has touched in a long time or you are running on a test system where the cache isn't populated (yet)?
Else you just don't have enough RAM available to cache most of the relevant data in your DB. Consequently, random access is much more expensive than sequential access when data resides in cache. Depending on the actual situation you may have to adjust to get better query plans.

One other factor has to be mentioned for slow response on the first read only: Hint bits. Read details in the Postgres Wiki and this related question:


Why does a SELECT statement dirty cache buffers in Postgres?


Or the table is extremely bloated, in which case an index scan would make sense and I would refer back to CLUSTER / pg_repack in my previous answer that you quoted. (Or just VACUUM FULL) And investigate your VACUUM settings. Those are important with many inserts and updates every day.

Depending on UPDATE patterns also consider a FILLFACTOR below 100. If you mostly update only newly added rows, set the lower FILLFACTER after compacting your table, so that only new pages keep some wiggle room for updates.


What fillfactor for caching table?
Are regular VACUUM ANALYZE still recommended under 9.1?


Schema


  campaign_id is 99%+ NULL and dt_updated is 0% NULL.


Adjust the sequence of columns slightly, to save 8 bytes per row (in the 99% of cases where campaign_id is NULL):

CREATE TABLE traffic (
    uuid_self       uuid not null REFERENCES ... ,
    uuid_partner    uuid not null REFERENCES ... ,
    id              serial PRIMARY KEY,
    impressions     integer NOT NULL DEFAULT 1,
    clicks          integer NOT NULL DEFAULT 0,
    campaign_id     integer,
    dt_created      DATE DEFAULT CURRENT_DATE NOT NULL,
    dt_updated      TIMESTAMPTZ DEFAULT CURRENT_TIMESTAMP,
);

Detailed explanation and links to more:


Configuring PostgreSQL for read performance


To measure:


Measure the size of a PostgreSQL table row