Trying to add a new category
It is such a long time since I set this up I have forgotten how to do this.
Trying to ADD Music Videos
I assume that you are talking about the Customize View procedure. I'm not an expert on this, but the word 'Category' only appears to be relevant in your basic choice of view. The 'View As' dropdown lets you choose between Panes, Categories, 3D, File List, and Chart. If you choose to view as 'Categories' then you would follow that by clicking the Add button to select one of the existing metadata fields. If no suitable metadata tag exists you would have to create a new one.
In other words, I don't think you ever create new categories, you just define what tags you want in a 'Categories' view.