As a test:

If you give the user "Owner Permissions" to your Calendar, can they create a new "Category" in the Shared Tasks? I think the master category list permission originate from the Calendar permission.

Try it out.

Good Luck!