シンプルに手順だけを考えると
1)商品とカテゴリの関連付けデータを全て削除（関連付けを外す
2)カテゴリデータを全て削除（カテゴリを無くす
3)新しいカテゴリデータを投入（新しいIDを振ったカテゴリCSV等で
4)カテゴリIDのシーケンス値を設定（DBの管理ツールなどで）
5)新しいカテゴリに対して商品の関連付けを行う（商品編集等

となると思います。
作業前の商品とカテゴリの関連付け状態を維持したい場合は、
作業前のカテゴリと新しいカテゴリの間でIDの対照表を作り、商品とカテゴリの関連付けデータに対して更新をかける必要があると思います。
商品が少なければ手動で関連付けし直しても良いと思いますし、商品が多くて手動で付け直しをしたくない場合などは、上記の流れを含めて自動化するプログラムを組む必要があると思います。

----------------
EC-CUBE公式エヴァンジェリスト
EC-CUBEインテグレートパートナー (株)スピリット・オブ
移転・拡張・高速化・問題解決
各種カスタマイズ・支援依頼承ります。
[url=h