Hello;
I said I had such problem with another member using a virtual host and a Plesk interface.
His host answered us that there was no solution, due to their users restrictions.
And we had effectively to :
1- create the new category in the gallery Admin Control Panel
2- go into the Plesk interface, and file manager
3- delete this category created by the "apache user"
4- re-create this category, assigning CHMOD 777
... each time we needed to create a new category. I don't know about your host's restrictions, but in our case, that was the only way to keep it working without changing host.
Hope you will find your way.