Hello,
JoomSEF does not store the site domain, it only stores the relative URLs starting with index.php... .
So movement to other domain should not have effect on this.
More likely, the URL rewriting (mod_rewrite) is not enabled or configured correctly on the new server. Or there is some otherconfiguration directive interfering, such as (Option FollowSymLinks). Please check with your new server admin that the configuration is okay.