Don't do it by going directly to Categories under the File menu.  Instead, go
to a Contact Record, then click Category, then Master Category List, type in
new Category, hit Add, Ok, and now it will be there to use.  Strange that it
doesn't save it the way you were doing it, but this way works - something
about having to be in a record for it to work.