Same story here.
Adding New Category via K2, no any tricks, just giving it a name and alias, saving, closing - nothing appears in Categories list. list of categories is empty.
Clean install of J1.7.3, two languages, default on front page is NOT English. Changing it to English doesn't give any better result - category list is still empty.
BUT when I try to create an ITEM, there on page with all fields about ITEM, in drop-down list "select category" there ARE all categories I've created while trying' and testing..
Creating item, and it also doesn't appear in list of items.. Reinstall didn't help..
Safari 5.1.1 (don't know, will this help?..)