Are you sure that you have changed all the configuration files? Grep for the old domain name.

Have you changed the s_cscf table in the icscf database? It contains the list of all your S-CSCFs.

Check the imsu table in the hss_db database. It might be that you have IMS Subscriptions that were left as registered in the old S-CSCFs and now the HSS/I-CSCF are trying to redirect you there. Clear the values in there.