Some Antivirus software / applications will lock certain system files and program files and when the uninstaller attempts to access these files you will receive an error that you must first install or repair Replay.
***This behavior has been confirmed when the core or agent is running ESET Security Software Antivirus and Kaspersky***
First, attempt simply disabling the AV software in the Management Console or Task Bar and try the uninstall of replay again thereafter.
If you are prompted with the same message that you must install / repair, then proceed to disable the AV services on the Core / Agent and try the uninstall of Replay again.
You should not need to go to extremes such as uninstalling the AV platform being used on the server in question but if the Replay uninstall continues to display the same message you will need to look at Microsoft Uninstall Tools as the install may be broken.