You can do this by setting the categories_id for each product in the products_to_categories table from 0 to categories_id 1 ...
First, backup your database ...
Next, this will change all Products from being in the Top Level Category of categories_id 0 to categories_id 1 ...
Then run the following in the Tools ... Install SQL Patches ...
Code:
UPDATE products_to_categories SET categories_id = 1 where categories_id = 0;
Next, go to the Catalog ... Categories/Products ... and you should be able to click the NEW CATEGORY button ...
Create a Category and when done, all Products should end up in this new Category ... if not, check what categories_id your new Category is and this can be updated on the products_to_categories table after a couple or three additional questions, should this problem arise ... otherwise, you should be set now and can build your Categories and move your Products around to proper Categories ...