Unable to add selected web parts Error message when adding a Web part to a list or library page

You have a list or document library page (allitems.aspx) and you are trying to add a Web part. You get an error message:
Unable to add selected Web part(s). (name of Web part): The file is not checked out. You must first check out this document before making changes.
Publishing features are not turned on and it is not a page that lives in a library accessible by the GUI.
Solution:
Open the site in SharePoint Designer and check out the page. Then, check in the page after modifications are done. It seems like this is just a bug.

Alternatively, you can turn off "require checkout" in the document library, add the Web part to the page, then turn on the require checkout again after you make your changes.