Solution 1:

Amazon EC2 instances should be thought of as temporary, we have about 100 running and about 10% die every week, we just kill them off and start again. Just create a new instance from the EBS image (You created an EBS image right? ;) ).

At first I thought this was a bit odd for so many instances to fail on such a regular basis but I contacted AWS support and they said pretty much what I said above. Infact I don't think I've ever had an instance running for longer than a month without it failing (Although we do hammer all our instances, they're on 100% CPU pretty-much all the time)