Keep checking fuses, one is blown.
Make sure you check all of them in the car & under the hood, regardless of the label. The radio memory wire is commonly fused together with the dome light, cig lighter, etc.
The fact that your radio works without constant power tells me that you don't have it wired right. It sounds like you have the red & yellow from the deck wired together to switched power. You'll need to fix this before the deck will keep memory. The yellow wire from the deck needs to be wired to constant power.
Let me know if you need anything else.