A few days ago my computer hang and I had to reboot. Now when I boot the following happens:

Auto-Detecting Pri master... Not detected
Auto-Detecting Pri slave... Not detected
Auto-Detecting Sec master... Not detected
Auto-Detecting Sec slave... Not detected

I have a HDD as Pri master and a CD-RW as Pri slave. I don't understand why they aren't detected. So I tried to switch the cable that goes from the power supply to the CD-Drive and HDD, and then it booted and my computer worked for almost an hour before it hung again. Then today I managed to get lucky again and it detected my IDE devices but after an hour or so it seemed like it lost its connection and the computer hung again.

I'm suspecting that it might be something with the power supply since switching the cables worked for a little while. I have an AMI BIOS and have not changed either HDD or CD-Drive.

Your power supply is probably about to die... PSU are cheap these days. It probably doesn't provide enought power to turn on all the IDE device thought you have enought to power (which is somehow strange, my computer was just turning off when the PSU was unable to provide the needed power). I suggest you to try with another power supply first before buying a new one, it might be something else.
*****BIG FAT WARNING******
Make sure to CAREFULLY plug back the new power supply. A PSU pluged the wrong way will kill your motherboard (usually there is no way to plug it the wrong way, but old AT PSUs don't have that kind of protection). Same about the "power" and the "reset" connector on the board... Make sure you plug them the right way, I saw computer to turn on fire because of reset cable pluged on the wrong pins.

I tried with a brand new power supply. The old one provided 350W and this one 520W. But the problem persists. And now I'm out of ideas on what might be causing the problem.

this is strange indeed. Have you tried the drive and the cd-rw on another computer? It is very unlikely they both died at the same time, but who know...
Also, try to plug drives on different cables, there is some chance one of those is defective and is "corrupting" the entire IDE bus, preventing the BIOS to detect the second drive (but in this case it is quite strange it doesnt hang at POST).