The backup set holds a backup of a database other than the existing
This is a type of safety check done by SQL Server so you don't by mistake overwrite the wrong database.
I believe it includes things such as that the destination database exists and the name of the destination database isn't the same as the name of the database you have in the backup. Possibly a few more things.
So double check and triple check that you connected to the right SQL server etc.
But the REPLACE option should override that safety check, that is why it exists! So make sure that you are 100% certain that you executed with the replace option.
You can of course first delete the destination database since the RESTORE will (internally) do it for you anyhow, and then do the restore.