So, yeah, I'd put the 3600x back in, then check to see what BIOS version is installed. If it is not a new enough BIOS version to support the 5900x then you will need to update the BIOS to a version that supports it and I generally recommend simply keeping the system updated to the latest version at all times anymore. BIOS updates these days are often practically as mandatory as driver updates due to changes in Windows, new hardware, bugs and fixes that are found, security vulnerabilities and refinements to the tuning for various features.
Once you update to the latest version, then try the 5900x again. I wouldn't worry terribly about replacing the thermal paste in between CPU changes until you get it to work. Just make sure it works and THEN clean the cooler and top of the CPU and apply fresh paste before final reassembly. Not much point in going through all that if the CPU still doesn't work after updating the BIOS.
Did you buy this CPU new or used and WHERE did you buy it from?