That message does NOT come from CUCM, so I would look at debugs from your GW to find out if the call is making it out, and what the telco is replying.
Review all your basics regarding call routing.
Yes, power failures can cause data corruption in the server HDD's and you can have any number of problems from that, however, in your case, given the message that you're receiving, this doesn't seem to be the case.
If you need more assistance troubleshooting this, you can open a TAC case.
HTH
java
if this helps, please rate