Why you might be getting Solution Installation or removal failed on Publish of a custom solution
Just the other day I was working in a demo environment and went to publish some changes in a custom solution when I was presented with the following message:
Tried again and got the same message so I clicked on the "See Solution History" link and then as nothing obvious appeared in the default view, changed to the "Internal Solutions History" view which then gave me this:
The core Dynamics 365 CE solutions were obviously being updated in the background and I was concerned that the "Failure" in the Result column was the cause of the issue. However, as it turns out, I didn't need to worry because after a period of time that "Failure" changed to "Success" and a number of other background solution updates were processed in a similar way. Once all the updates are complete, I was then able to publish the customisations as usual.
In short, if you get this message it is not necessarily a reason to panic, check the Solutions History first to see if Custom or Internal solutions are being updated at the same time you are trying to publish.