I had this problem on a Debian box I was configuring. It turns out the fix was Apache-involved, not WordPress.
WordPress version:
2.8.1
Apache version:
Apache/2.2.9 (Debian) PHP/5.2.6-1+lenny3 with Suhosin-Patch
Problem:
mod_rewrite would not produce Permalinks.
Fix:
See WordPress Codex: http://codex.ww.wp.xz.cn/Using_Permalinks#Using_.22Pretty.22_permalinks
I added the above information to my /etc/apache2/sites-available/default (choose your site) under the <Directory /> and <Directory /var/www> (choose your directories accordingly), viz.:
Options FollowSymLinks (hint: this one was already there)
AllowOverride FileInfo
AllowOverride All (this was set to None by default)
