Query got slow from 9.0 to 9.1 upgrade

We just upgraded from 9.0 to 9.1, we're using the same server configuration, that has been confirmed 3 or 4 times over. Any help would be appreciated. If I remove the "ORDER BY" it gets fast again because it goes back to using the user_id index, if I remove the LIMIT/OFFSET it gets fast again, obviously I need both of those, but that was just to test and see what would happen.

Query: SELECT * FROM bookmark_groups WHERE user_id = 6708929 ORDER BY created DESC LIMIT 25 OFFSET 0;

explain analyze from 9.0:

Limit (cost=1436.78..1436.84 rows=25 width=99) (actual time=15.399..15.403 rows=25 loops=1)
-> Sort (cost=1436.78..1438.67 rows=757 width=99) (actual time=15.397..15.397 rows=25 loops=1)
Sort Key: created
Sort Method: top-N heapsort Memory: 28kB
-> Index Scan using bookmark_groups_user_id_idx on bookmark_groups (cost=0.00..1415.42 rows=757 width=99) (actual time=0.011..9.953 rows=33868 loops=1)
Index Cond: (user_id = 6708929)
Total runtime: 15.421 ms

explain analyze from 9.1:

Limit (cost=0.00..1801.30 rows=25 width=101) (actual time=1565.071..5002.068 rows=25 loops=1)
-> Index Scan using bookmark_groups_created_idx on bookmark_groups (cost=0.00..2592431.76 rows=35980 width=101) (actual time=1565.069..5002.062 rows=25 loops=1)
Filter: (user_id = 6708929)
Total runtime: 5002.095 ms

DDL:

CREATE TABLE "public"."bookmark_groups" (
"id" int8 NOT NULL DEFAULT nextval('bookmark_groups_id_seq'::regclass),
"user_id" int4 NOT NULL DEFAULT NULL,
"version" varchar DEFAULT NULL,
"created" timestamp(6) WITH TIME ZONE NOT NULL DEFAULT now(),
"username" varchar NOT NULL DEFAULT NULL,
"labels" varchar DEFAULT NULL,
"reference" varchar NOT NULL DEFAULT NULL,
"human" varchar NOT NULL DEFAULT NULL,
"highlight_color" char(6) DEFAULT NULL,
"title" varchar DEFAULT NULL,
"version_id" int4 NOT NULL DEFAULT NULL,
CONSTRAINT "bookmark_groups_pkey1" PRIMARY KEY ("id", "reference")
)
WITH (OIDS=FALSE);
ALTER TABLE "public"."bookmark_groups" OWNER TO "dev";
CREATE INDEX "bookmark_groups_created_idx" ON "public"."bookmark_groups" USING btree(created DESC NULLS FIRST);
CREATE INDEX "bookmark_groups_user_id_idx" ON "public"."bookmark_groups" USING btree(user_id ASC NULLS LAST);