パーマリンクの設定後、１度は適用されるも変更を加えると404になってし

色んな手段を試みてはみたのですが、どうしても解決しなかったのでご相談させてください。

WordPressを導入後、パーマリンクの設定を行い、この直後はすんなり設定が反映されるのですが、一度でも何かページの編集をしてしまうと、存在する全てのページが404エラーになってしまいます。

この状態でWordpressの元のURL（/?p=xxx）などにアクセスすると、パーマリンクに設定したスラッグにURLは置き換わるものの表示は404エラーとなってしまいます…。

試したこととしては
・Wordpressの再インストール
・Wordpressのテーブルを一度削除しての、再構築
・プラグインを停止した状態でのパーマリンクの変更
・mod_rewriteのテスト（問題なし）
・.htaccessも自動で書き換わっている。

上記のことを試しましたが、解決しませんでした…。
なによりも、一度は設定通りにパーマリンクが反映されるにも関わらず、一度編集を行ってしまうと404エラーになるというのがどうしても分かりませんでした。何か解決策はありますでしょうか。

サーバーは、アルファメールダイレクト
Wordpressのバージョンは3.3.2

となります。
宜しくお願い致します。