Ubuntu 8.04上でWordPress3を動かして、管理画面で作成した固定ページのパーマリンクを変えた時、404 Not Foundエラーが出てしまうので半日はまった。
最初、WordPressの設定が悪いのかと思って色々設定を変えたが変わらず。
ネットで調べていると以下のページでApacheのrewriteモジュールが有効になっていないことに気づく。

WordPressでパーマリンク設定後に404エラーが出る場合

以下のコマンドでRewriteモジュールを有効化する。
sudo a2enmod rewrite

Apacheのサイト設定ファイルのディレクトリ設定のAllowOverrideをAllに設定する
/etc/apache2/sites-enable/000-xxxx

Options FollowSymLinks MultiViews
AllowOverride All < -- 変更 Order allow,deny allow from all

Apacheを再起動する。
sudo /etc/init.d/apache2 restart

これで変更したパーマリンクをブラウザで指定すると該当ページが表示されるようになる。