There seems to be a limit to the number of categories the Attributes plugin supports. If you have a large number of categories, this plugin won't work. I have 1000 categories and I am unable to deselect all categories because there is no option to deselect! Not an issue if you are under the limit but it is if you are over. If you are over the limit and want to assign to all categories, the only option is to delete the custom field and start all over again but not select any categories.

So I found this:

For table t_attribute you may need to increase length of field s_category_id (from varchar 1000 ideally to varchar 5000)

That solves the problem of not being able to de-select all categories, which was the biggest problem! However, I can't select all 1000 categories and de-select only 6. That is ignored and the attribute still applies to the 6 categories that I de-select.

@LeeNewman
Yes each plugin that use just category list will experience this limit. You need to manually increase size for category IDs in database table (usually called s_category_ids).
Anyway Osclass with more than 600-800 categories may experience similar difficulties.