In addition, I also saw reference to making sure kb4474419 was installed successfully. I have checked my install history and both is one and kb449028 were installed successfully.
Is it possible that these have to be installed again for kb4516065 to work? Who knows but this is frustrating.
In my case KB4474419 was previously installed. However, Microsoft recommends that KB4516655 also be installed before KB4516065. KB4516655 would not install on my PC until I installed KB4490628. So, you might confirm that you have KB4516655 installed as well.
Here are the Microsoft Update Catalog links if needed for manual install in the order that I installed each one.
https://www.catalog.update.microsoft.com/Search.aspx?q=KB4490628
https://www.catalog.update.microsoft.com/Search.aspx?q=KB4516655
https://www.catalog.update.microsoft.com/Search.aspx?q=KB4516065
OUgrad