Although the 'Add Label' functionality shows, and a user can press it and enter a name for the label they wish to create, they are not able to actually save the new label against a Visual Task Board unless they have the 'global_tags_creator' Role.
Upon taking focus off the newly created label the user is confronted with the 'You do not have permission to create label' error message in the UI.
Giving users the 'global_tags_creator' Role then means they can create tags globally within the application, which might not always be desirable.
This is expected behaviour. As per the Configure Visual Task Boards labels section of the New York documentation,
"Users with global_tags_creator role can add more labels to the board and rename the label"
PRB1348590 was previously raised for this behaviour, which was closed as 'Working as Expected'.
As a workaround you can look to set the 'glide.vtb.check_global_tags_creator_role' System Property to false.