My setup is as follows: I am syncing to a special/custom contacts folder in Outlook which I created under my Gmail account. (I don't want my Google contacts to get mixed with my other Microsoft contacts, which I have in the default Outlook folder.)
Syncing contacts works OK in all aspects except for Google labels (=Outlook categories).
The error can be reproduced as follows:
The only solution seems to be to delete the categories from affected contacts, contact by contact in Outlook (a lot of manual work).
Please note: I cannot simply delete the whole offending categories in Outlook, since in the category list there is a comment "Not in the master category list" and the "Deled" button is grayed out. This could be due to my setup, since I am not syncing Google contacts to my main Outlook contacts folder, but to the custom one, as explained above.