|First check to see if the sound is coming through the on-board speaker (if you have one). Sometimes that is a warning that overheating or a fan not spinning up is occurring.|
It's possible the sound stopped when you replaced the power supply because you were inside the case and unknowingly fixed it temporarily.
But if it is the PSU the fan is the likely culprit. Either bearings wearing out or something brushing against the blades. You may be able to temporarily stop the fan from spinning by holding it with your finger. Be careful if you use a screwdriver as shoving it in a moving fan can break the fan blades. But if the noise stops then the fan is the problem. You can try that also with any case fans it may have.
Can you give any more details on what the 'loud horrible noise' sounds like? If it's a whining then fans would be likely. If it's more sharper then an electronic component might be at fault. But if that's what it is I doubt the PSU will last much longer