Hi Guys,
I hope this solves your problem like it did mine (I don't have multistore in my setup but shouldn't be a factor).
Log into the admin area of your store.
Step 1: Create your category as usual.
Catalog -> Categories -> Add new
Step 2: Click on modules -> modules
Step 3: Search for "Top Horizontal Menu" in the modules window
Step 4: Click "configure"
Step 5: In the settings frameset, scroll down in the first box on the left, till you get to categories sub section. Select your desired category and click "Add".
Your category will be added to the right box.
Click "Save".
Step 6: Refresh your store.
Do let us know if this works for everyone.