Normally, in every version of WP I've used, a new category won't appear on the blog until one post has been made to that category.
That said, puzzled 94, it sounds like something(s) is really wrong with your WP install -- because sorting out the category links on the blog is a different issue than not being able to add new categories at all. Or do you mean that you reinstalled and now everything's fine?
In either case, you can go to the Options > Permalinks page to reset your URLs; perhaps that's all that's wrong.
Otherwise, I would start another thread with the above information, including enough information for others to determine what's wrong.