I was trying to change the Anonymous Access settings for a list, as per this screen:
However, when I checked the "Add Items" box and clicked OK, it did not save the changes. Everytime I repeated this and went back to the screen, the "Add Items" box was not checked.
The cause of the problem was that the Anonymous Policy for the SharePoint Application (that hosted the site) had been changed. By default this is set to "None". However, it had been set to "Deny Write".
There wasn't a good reason for this and switching it back to "None" fixed the problem.