Sytmptom:  

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.