Slow Query Help

We upgraded from PG 9.1 to 9.2. Since the upgrade, the # of active queries has raised significantly, especially during our peak time where lots of users are logging in.  According to New Relic, this query is now taking up the most amount of time during peak activity and my pg_stat_activity and slow log sampling agrees. We have 3 DB servers referenced here, production running 9.2.2, semi-idle (idle except for replication when I ran the test) running 9.2.2, and 9.1.3 completely idle with an old dump restored. 

HW: All servers have the same amount of RAM and CPU and all our indexes fit in RAM. HD's differ, but they're all SSD and since the explain analyze's are all indexes, I'm going to assume it doesn't mean that much in the context. 

Configuration across all three servers is the same.

Table was auto vacuumed today.

Idle DB running 9.1.3

http://explain.depesz.com/s/7DZ

Semi-Idle DB running 9.2.2 (transactions ran previously and replication happening, but no active traffic when query was ran)

http://explain.depesz.com/s/fEE

Production DB running 9.2.2 (Incredibly Active)

http://explain.depesz.com/s/qVW

                                       Table "public.users"

      Column       |           Type           |                     Modifiers                      

-------------------+--------------------------+----------------------------------------------------

 id                | integer                  | not null default nextval('users_id_seq'::regclass)

 created_dt        | timestamp with time zone | default now()

 last_login_dt     | timestamp with time zone | default now()

 email             | character varying        | not null

 verified          | boolean                  | default false

 first_name        | character varying        | 

 last_name         | character varying        | 

 username          | character varying(50)    | not null

 location          | character varying        | 

 im_type           | character varying        | 

 im_username       | character varying        | 

 website           | character varying        | 

 phone_mobile      | character varying(30)    | 

 postal_code       | character varying(10)    | 

 language_tag      | character varying(7)     | default 'en'::character varying

 settings          | text                     | default ''::text

 country           | character(2)             | default ''::bpchar

 timezone          | character varying(50)    | not null default 'UTC'::character varying

 verify_hash       | character varying        | 

 bio               | character varying(160)   | 

 twitter           | character varying        | 

 facebook          | character varying        | 

 search_updated_dt | timestamp with time zone | not null default now()

 source            | character varying        | 

 auto_verified     | boolean                  | 

 password          | character(60)            | 

 google            | character varying        | 

 gender            | smallint                 | not null default 0

 birthdate         | date                     | 

 weibo             | character varying        | 

Indexes:

    "users_pkey" PRIMARY KEY, btree (id)

    "u_auth_email_index" UNIQUE, btree (lower(email::text))

    "u_auth_uname_index" UNIQUE, btree (lower(username::text))

    "u_auth_verify_hash_idx" UNIQUE, btree (verify_hash)

    "users_search_updated_dt_idx" btree (search_updated_dt DESC)