Weird behavior of Categories menu

I am presently using: v1.3.9g with the estorenow template. So this is the situation:

I have categories on the left hand side box. For example I had the shoes category listed by brand, everything cool, now when I add a subcategory it disappears from the menu box and instead it displays the only the subcategories such as Man and Woman.

The image I am attaching shows how Adidas and AF1 vanished from the menu tree which starts with the following brand Air Jordan. The site is at http://www.nikeguru.com

Thanks in advance!

Yes, that is weird behavior.
The only thing I can say from here is that the template has customized tpl_categories.php to show the categories in nested <ul> lists, but the nesting is not correctly done. The sub-subcats (Men, Women) are in the same list with the subcats (Air Jordan, etc.) instead of being in a lower nested list. The list items with subcats have an empty <ul></ul> if they are not open to the subs.

These inconsistencies make me suspect that there is also some coding problem with the categories box that is hiding subcats with subcats. You should ask the template's maker what is causing this behavior, and request that they correct the list nesting. I might be able to see the problem if you post the file.
Alternatively, you could replace the template's categories box with Categories Dressing, which has correctly nested lists and is known to function properly.

Thanks for the reply. How do I proceed with the replacement?

Download Categories Dressing from Free Addons, and follow the instructions in the readme. You would first want to save the template version of tpl_categories.php somewhere else (like your local computer) just in case you need it for something.