SOLUCIONADO.
Por si a alguien le ocurre lo mismo, debe probar dos cosas:
1) Con algún explorador con opciones root, montando las opciones r/w, buscar en todo el equipo el nombre del programa que da el problema, borrando todos los archivos que aparezcan.
2) Si tienes LuckyPatcher, arrancarlo para que se actualice todo el registro y si el programa que tenías instalado estaba verificado por éste, se borrará.
Tras reiniciar el equipo con estos dos pasos y volver a instalar desde cero la aplicación, ya ha funcionado correctamente.