I have no inside information on this, but generally speaking about Windows ...
Uninstall of the new version - cannot see how that is the culprit. But a proper uninstall of the previous version, is probably the issue. Uninstall is just another program (of the old version), which can fail OR perhaps it is not even supposed to work if you did not reboot. I mean, the OLD service might be hanging around (in registry or somewhere) after running the uninstall, while a reboot will only get rid of it ... and only after that the install of the new version is successful.
You also mentioned a concept of "full uninstall", which can mean many things - running a cleaner software, reboot, removing manually entries from registry, a second reboot, removing files under program files ... and that sort of things, not necessarily in the order I wrote them. Not sure what you did.
Sometimes, things like these happen. The fix is not to the new version, but an Utility, which will clean up the system ... like I said in the beginning, I don't have any inside information on the software.