新規投稿したら404エラーに…

パーマリンクの設定に疑問があります。
試しにタイトルをまったく別のもの（testとか）で投稿してみてください。
投稿がうまくいった場合、カテゴリーかタイトルに問題があるのでしょう。

パーマリンクが/%category%/%postname%/である場合、同じカテゴリーに同じタイトルで記事を投稿すると同じアドレスの別記事が複数存在してしまいます。
通常同じタイトルの場合「タイトル-2」などのように自動的に数字などが付与されると思いますが、何らかの影響で付与されなかった場合上記のようなことが起こることでしょう。

もし上記の件に当てはまらない（どんなタイトルでもエラーになる、パーマリンクをデフォルトにしてもエラーになる）場合は、サーバーを疑ってみてください。
何らかのバージョンアップなどがなかったか、障害報告は出ていないかの確認が必要です。