Okay, I'm a lamer. But maybe I can still be a hero for some of those banging their heads over this...
After chewing out geniuses that build this software, I took my own advice and ripped out my entire Wordpress directory and database and restored them to an older version. But I still got 404 on my %category%/%postname% permalinks!
This clearly meant it wasn’t the Wordpress 2.7.1 update.
So, after a couple of WTFs, it occurred to me that it had to be permissions or the Apache server configuration. (I’m not a programmer, but I do hack a little admin here and there.)
Anyway, first I ran my usual Wordpress premissions commands: chmod -R 644 * and then chmod -R +X * and made sure permissions were okay. But still, I got the 404s.
So next, I grudging began scanning, line by line, through the httpd.conf file (which has moved a few times over the years and is now located at /etc/httpd/conf/httpd.conf in Fedora) and there it was! Properly placed between the <Directory> section was the AllowOverride directive set to none!
Of course when the AllowOverride directive is set to none, the .htaccess file is completely ignored! So I quickly set it to all and BAM! everything worked.
Of course, you may not want to set AllowOverride to all as there are other ramifications besides making your pretty permalinks work. But that’s something you can read about (see http://httpd.apache.org/docs/1.3/mod/core.html#allowoverride) after your blog is serving up pretty linked pages.
Hope that helps someone. And again, sorry to all you hard working Wordpress project people.