Unfortunately, it did not work.

I ran the following with no success.
Admin -> Tools -> Store Manager, and click on "Reset ALL Products Master Categories ID"

also ran
Admin -> Tools -> Store Manager, and click on "Reset ALL Products Price Sorter"

No luck.

So the question is, if someone creates products under main category, and then decides to create sub-categories, then what is the proper way to move products to those newly created sub-categories?

Apparently Admin's move function did not work in this case!