Hi MAK –
Well, after spending entirely too many hours sifting through the same messages and falling into the foulest of moods during the endeavor, I can offer this clumsy advice in order to fix mysteriously broken permalinks:
RE-INSTALL WORDPRESS FROM SCRATCH, change the permalink structure once and then don’t mess with it again.
(the caps are for the benefit of those who scan these boards. I’m not yelling, really…)
I deleted everything but wp-content, including the database. Then I uploaded all the WP files anew, stuck in a completely blank .htaccess, and ran install.php.
Then I imported my old database from a backup, and THEN I switched my permalink structure, and now everything’s as it should be.
…fingers crossed.