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.
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.