increasing LIMIT with ORDER BY changes queryplan (7.4)

Hi everyone,

I'm new to postgre so please don't take anything implied but rather throw
questions when something's unclear.
Here's my problem or rather my question: I have a table with a category
(four different values here), some data-fields I need and a few
timestampfields indicating when which datafield was last updated. I've set
up Indexes on the timestampfields with HAVING category = 'foo' since I found
that to give me a serious performance boost (I usually query just one
category at a time).
Table has about 9 million rows.
I'm querying with
SELECT "id", "title", "subtitle", "submissions" FROM "mytable" WHERE
"category" = 'foo' ORDER BY "last_update_submissions" ASC LIMIT 50
and it's working fine, speed is ok.
EXPLAIN says:
---snip---
Limit (cost=0.00..2248.88 rows=50 width=434)
-> Index Scan using index__last_update_submissions__category__foo on
mytable (cost=0.00..531590.39 rows=11819 width=434)
Filter: ((category)::text = 'foo'::text)
---snip---
where index__last_update_submissions__category__foo is my special index.

When I increase LIMIT though, it get's strange.
with LIMIT 1899 it's still the same queryplan, on LIMIT 1900 it changes to:
---snip---
Limit (cost=85409.87..85414.62 rows=1900 width=434)
-> Sort (cost=85409.87..85439.42 rows=11819 width=434)
Sort Key: last_update_submissions
-> Index Scan using index__last_update_submissions__category__foo
on mytable (cost=0.00..82989.63 rows=11819 width=434)
Index Cond: ((category)::text = 'foo'::text)
---snip---

and, as guessed, takes forever. tried to ANALYZE the table but no change.
Anyone got any ideas? I just don't understand why it's sorting the values
while the index should already be sorted...

Oh, btw, I'm on 7.4 (sarge stable version). Could this behaviour change if I
just upgrade to 8.1?

any input is appreciated - it's not a critical project but just a private
one I'm using to get familiar with postgre.

greets from hamburg, germany,

jan harders