It may have something to do with your permalink structure.
I believe that they recommend setting your permalink structure to start with a number like date based or even %post_id%.
Is this still an issue with the latest ver of WP?
I believe that they have already found a solution to the permalink issue and that it will be included in one of the upcoming updates. I could be mistaken, I just remember reading that somewhere.
Oh, on that same site.
Andrew Nacin said on June 23, 2011:
Well, and to answer a question from above, “Also, what are the chances that WordPress will have a fix for this in a future version?” — the chances are great that we’ll be removing all performance penalties for %postname% in the release of WordPress 3.3, due later this year.
Andrew Nacin said on August 17, 2011:
I just want to confirm that WordPress 3.3 (due in November) will indeed remove all permalink performance issues related to %postname%, %category%, and the like. It’s done and currently in trunk. So look for that in the coming months.