I recently installed Wordpress on an Ubuntu 8.10 image and permalinks wouldn’t work properly. I would only get a 404 File Not Found error when I enabled the pretty URL permalink structure. The Permalink function in Wordpress relies on a small URL rewrite statement that Wordpress puts in the .htaccess file at the root folder of your WP installation:
# BEGIN WordPress
Turns out there is a setting in Apache that disables the .htaccess files by default. So you have to enable this to allow the .htaccess files to be processed. The setting is called AllowOverride, and you must set this to All (it probably is set to None right now).
Change your Apache virtual host config file to something like this:
<VirtualHost *:80>
ServerAdmin webmaster@server.com
DocumentRoot /var/www/
<Directory />
Options FollowSymLinks
AllowOverride All
</Directory>
<Directory /var/www/>
Options Indexes FollowSymLinks MultiViews
AllowOverride All
Order allow,deny
allow from all
</Directory>
....