Have you uninstalled and re-installed Fusion since reinstalling macOS? Perhaps the macOS reinstall nuked something that Fusion had set up during its installation.
Will uninstalling delete all my Virtual Machines and their configs as well? I have many VMs and I'm not sure if I want to reinstall them all...
Uninstalling Fusion will not touch your virtual machines. Think of it this way: if you have Microsoft Word installed and you delete it, do your Word documents disappear?