If you’re Wordpress 2.0 permalink structure is not working under PHP 4, check your Category Slugs and Post Slugs and make sure there aren’t any spaces or Upper Case characters!!!
I just figured this out after days of troubleshooting.
I’m using /Êtegory%/%postname%/ without any problems at all now. 
It happened to me because I imported outside content with uppers and spaces and everything.