The event id 13 is happening because you need to put the domain controllers group for your new domain into the CERTSRV_DCOM_ACCESS group - this may be a domain group if your CA was on a DC, otherwise it would be a local group on the CA box.
Since the name of the CA changed due to the rename, the only real way around this is to reinstall with a new certificate. To best avoid issues, it would be best to completely remove the old CA from AD prior to reinstalling it.
I would also recommend taking a full backup including system state and archiving that for a bit, just in case you need to restore the old one. Or just take the box offline and physically archive it.
How to decom a CA server properly from AD:
http://support.microsoft.com/kb/889250