This bug does not happen now, but is inherited from some previous bad release
This may be the key here.
If you ask a complete reinstall every time you release a new version, this looks indeed very unprofessional. It may be OK if the users don't customize your app, so losing previous configuration wouldn't be an issue. If they do and spend at least several minutes doing it, it will quickly become annoying: they will either install a similar app released by your competitor, or stop customizing it.
On the other hand, since there is a before and a now, and upgrading works well unless the user has a previous version, this situation is more common and somehow similar to breaking backwards compatibility. You can do one of the following:
Increment a version number and tell that upgrading from YourApp 3.0 to YourApp 4.0 requires a full uninstall.
If you're, say, at version 3.7.15, and the upgrade works well since 3.4.82, but not for 3.4.81, just document that such upgrade is not supported. If the user attempts to upgrade, the updater should indicate that the option is not supported and will result in the loss of preferences.
Finally, in all cases, backup users' preferences before doing the upgrade. This has two consequences:
If the upgrade fails, the user will be pissed off but will still be able to go back to the previous version without losing anything.
After a fresh install, you can use the backup to get some of the preferences you know to be fail-safe. Losing only a part of the preferences is slightly better than losing everything.