iOS4のユーザー辞書トラブル

関係あるかどうかわかりませんが、

設定 - リセット - キーボードの変換学習をリセット は試してみましたか？

復元をしましたがやはりユーザー辞書登録が出来ない状態は改善しません。

バックアップを使用せずに復元していますか？

バックアップに関しては、同期させていますのでバックアップされた後の復元の操作になることと思います。

復元には、バックアップからの復元と、新規iPhoneとしての復元の2種類があるはずです。

前者だと設定やアプリデータは保存されますが、壊れた設定等も書き戻されてしまいます。

個別のリセットが利かない場合には、後者の新規としての復元を行わないと問題は解消しません。

アプリ自体や音楽・写真等のデータは改めて同期し直せば問題ありませんが、アプリ固有のデータや各種設定は一から行う必要があります。

バックアップに関しては、同期させていますのでバックアップされた後の復元の操作になることと思います。

ではなくて、復元をするときにバックアップを戻さない復元（"新たなiPhoneとして設定"だったかな）をしたらどうですかということです。

追記：

Hit-Cさんともろかぶりでした…。

新規のバックアップも含めて

いえ、「新規のバックアップ」とかではなくて、「iPhone、iPad、または iPod touch を新しいデバイスとして設定する方法」です。