The problem was that the uninstaller was searching for the old installer, couldn't find it but not asking for the path to it.
The uninstaller asked for the path but I didn't have the .msi file anymore and it wasn't on the downloads page .
I filed a problem to support, and they gave me the solution - C168635
They made the old installer file available. Updating still didn't work as it wasn't asking for the file, just throwing out a generic error but uninstalling (with browsing to the downloaded .msi for the old version) and installing separately worked great.
They also suggested I install the new version to a new directory but I don't need multiple versions.
So, thank you FME Support Team! You're great!