64bitOSにおけるパーマリンク設定について

本日サーバのOSを64bitOS(Ubuntu8.04Server)に変更したところ、
個別記事のページや、ブログの2ページ目以降が表示できなくなってしまいました。
(NotFoundになります。)

パーマリンクを設定している為、php-mbstringが無い or Apache の AllowOverride の設定を疑いましたが、
php-mbstring はデフォルトで設定されているようですし、AllowOverride に関しては設定を変更したつもりです。

—————————————–<以下設定内容>———————————————————————-

[mbstring]
phpinfo()より
Multibyte Support enabled
Multibyte string engine libmbfl
Multibyte (japanese) regex support enabled
Multibyte regex (oniguruma) version 4.4.4
Multibyte regex (oniguruma) backtrack check On

mbstring extension makes use of “streamable kanji code filter and converter”, which is distributed under the GNU Lesser General Public License version 2.1.

Directive Local Value Master Value
mbstring.detect_order no value no value
mbstring.encoding_translation Off Off
mbstring.func_overload 0 0
mbstring.http_input pass pass
mbstring.http_output pass pass
mbstring.internal_encoding no value no value
mbstring.language neutral neutral
mbstring.strict_detection Off Off
mbstring.substitute_character no value no value

[AllowOverride]
[Apache2]-[conf.d] 配下に directory_settings ファイルを作成し、
以下のように記述しました。

<directory />
Options All
Options -Indexes
AllowOverride All
Order allow,deny
allow from all
</directory>

——————————————————————————————————————————

修正方法をご教授いただけませんでしょうか。

環境は
OS　Ubuntu8.04.1 Server
Apache 2.2.8 (Ubuntu)
PHP 5.2.4-2ubuntu5.3 with Suhosin-Patch
MySQL　5.0.51a
です。

宜しくお願いいたします。