Am I missing something here? Do I need to upgrade the boss, and import the categories on his Outlook, so she can see them in her Outlook?
Since Outlook 2007/2010 uses mailbox to store Master Category List (MCT) (in opposite to Oulook 2003 wich uses Registry for that purpose), she sees MCT taken locally from her storage (not globally from Registry). And her bosses mailbox doesn't contain MCT since he/she still uses Outlook 2003.
So you're right. After upgrading her bosses Outlook to 2010 and importing MCT there categories should become available.
Alternatively (if it's possible) she can open her bosses mailbox as default storage
and import MCT again.