Appending "LIMIT" to query drastically decreases performance

Can anyone explain the following odd behavior?
I have a query that completes in about 90 ms. If I append LIMIT to the
very end, eg. "LIMIT 500" the evaluation time increases to about 800 ms.
How can performance get *worse* by giving the database the option to
stop the evaluation earlier (when it reaches the output 500 rows)?

I have pasted both queries together with output from explain analyze here:
    http://pastebin.com/m3c0d1896