Did you remove the account from outlook and add it back using auto account setup?
In the web interface, they are called Contact lists and are listed under New and also under Lists. You can't view or manage categories on contacts in the web interface but can categorize them in outlook. (If they are assigned, you can use the Category list in the nav pane to view them, but not much else - more at the end.)
The master list online might have some white categories - these won't sync to outlook desktop. The white ones are automatic categories used for filtering online. They work more like Search folders- you can list them in the folder list and quickly filter the view. AFAIK, you can't delete them.
If the category has color, it will sync down.
In this screenshot, My Contacts is my only category and syncs. The others were used by the old outlook.com to filter mail.
These are the options- Show in folder pane lists the folder in the navigation pane so you can select it as if it's a Search Folder. Filter column adds it to the filter list under all in the message list. (See next shot) I cannot add, edit, or delete the predefined categories.
Only the personal categories sync to Outlook on the desktop. [It's possible that a future build will change this - so they might eventually sync down too.]
This is a test mailbox and most of the contents are newsletters - so most of the predefined categories are useless to me but I'll select some as an example. (The server automatically categorizes the messages as they arrive. )
If you want to view contacts in a category, you need to have that category on the nav pane - and can only use it in the Mail pane (although you can't do anything but view the list of names).