I ran into someone on #wordpress that had permalinks that weren't working. They had upgraded from WordPress 1.2 The problem was that their post slugs had triple dashes in it... like /my-post---title/ due to the original title being "My Post - Title".
The rewrite rules choke on this, so here is how to fix it.
NOTE: CHANGE THE PREFIX ON THE TABLE TO MATCH YOUR INSTALL!!!!
Go into phpMyAdmin.
Back up your database first!
Then go to the SQL tab.
Note: The forums eat backticks, which is the key under the Esc key and to the left of the "1" key... change the question marks to backticks. And don't forget to change wp_posts to match your posts table!
UPDATE ?wp_posts? SET ?post_name? = REPLACE(?post_name?, '---', '-');