Ok, just stumbled on a workaround. I was reading through the NSIS userguide and found this section:
3.2.1 Common Options
/NCRC disables the CRC check, unless CRCCheck force was used in the script.
/S runs the installer or uninstaller silently. See section 4.12 for more information.
/D sets the default installation directory ($INSTDIR), overriding InstallDir and InstallDirRegKey. It must be the last parameter used in the command line and must not contain any quotes, even if the path contains spaces. Only absolute paths are supported.
Now, when i create a new shortcut and manually provide the app location, the uninstall works. So I did the following: "C:\Program Files (x86)\NSIS\uninst-nsis.exe" /DC:\Program Files (x86)\NSIS
So me being me, I wanted to look at the registry for the NSIS installer, so I reinstalled to try again, and now "WITHOUT THE /D" everything has started to work again, even the other apps now uninstall fine!
Erm, soooooo, I dont get it ;-) Why (by adding/using "/D" on the NSIS unistaller), did that fix all other apps that had the unistall error????
Even though I hate endings like this, I seem to be all sorted now, but it would be nice to know why.