We not only created a lot of new categories, we deleted a lot of old categories and renamed some of them as well. Now the issue was to correctly assigning products to appropriate categories. We were provided product csv with three columns (category,sku,category-code). category-code was for SAP admins, so they can update their inventory according to code. But we need other two columns only. Here is the shell script I wrote which runs smoothly and does the work for me :-)
Magento - How to assign a product to a Category and It's parent categories