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.