I am having the same trouble.
I looked for the non-english that all of you are talking about but all i get is dead links.
here is what im trying to post:

Biker_Art_or_Graphics

this is the error:
Error: Unable to Add Category
There were problems with the following fields:

• Name (Invalid format)

Please fix any errors and submit the record again.

 Are you typing the cat name in manually or copy pasting it. If you are doing copy paste please paste it to notepad or any other plain text editor then copy from there and paste into the links form. Sometimes when you copy paste you take invisible content also that links can't work with.

This may not be the case, it's just something I have came across.

Mack.