What everyone has forgotten to mention, you have to activate the category. I’ve just spent 20 minutes beating my head up against the wall and searching the Magento site for an answer. Then I decided to take a closer look at the category edit pages.
Catalog > Manage Categories
Select the category you want active and scroll down and activate it.
It appears the “Root Category” doesn’t have to be active, however, if you have multiple levels of categories the parents do need to be active:
Root (not active)
If the category Cat is not active, then you don’t get to see the Toys sub-category of Cat.