But, the catch was: the problem persisted when I tried to use Wordpress 2.5.1. Hmmm...wonder what's up.
So today, I started thinking that it might be an Apache issue, rather than a Wordpress issue. So, taking a break from a massive project I'm doing (only so much performance data you can process before brain freeze), I started to poke around.
That did it. I was not letting Apache read the damn .htaccess file that Wordpress installed.
Excuse the thudding of my head on the desk.
Many apologies to the Automattic team. This user haz th dumb.