I just had the exact same issue with the too many custom papers problem followed by the easycare not finding the printer.
Hp has recently posted a new easy printer care download that has a "scrubber" (their term-not mine} that does a better job of uninstalling the previous version and clearing registry values.
I was able to re-establish connections after installing the new Easy care download, followed by an uninstall and reinstall of the color center software. In the process, my print driver was also removed, and that needed a reinstall as well.
Although all of this was a royal pain, it must have been better than a complete reinstall of the OS and applications.