All you have to do is go to your Zen Cart Admin and click on the TOOLS ... INSTALL SQL PATCHES ... and in the box enter:
Code:
UPDATE products_to_categories SET categories_id = 1 where categories_id = 0;
And then go back to Catalog ... Categories/Products ... and click on the NEW CATEGORY button that should now be show and ADD you first Category which should end up as categories_id and when you SAVE that new first Category all of your Products will "magically" appear in that new Category ...

Now, you can make your Categories and MOVE these Products to the right Category without having to delete them all and remake each one of them ...

If you don't care about deleting each Product that you already made, then delete each one ... otherwise, run that command after backing up your database ...