I’m not sure what your knowledge level is, so here are a couple of things to start with.
Check AD sites and services. Make sure that each geographic location has a site, the ip subnet in that site is correct and that the location DC is under the server folder for each site.
Also take a look at this article, specifically info on repadmin, command line utilitly or look up info on replmon, a gui utility. http://technet2.microsoft.com/WindowsServer/en/library/22764cb5-9860-4f8f-95e7-337df24edf741033.mspx?mfr=true
Both utilities are 2003 support tools that are located on the 2003 cd but you can download them from http://www.microsoft.com/downloads/details.aspx?FamilyId=6EC50B78-8BE1-4E81-B3BE-4E7AC4F0912D
Another possible issue could be a firewall blocking the replication ports. Here is a link to the ports AD uses
I would only demote/promote them again as a last ditch effort. Most likely the issue is a configuration issue that will not go away even if you tried this.
What errors are you getting in the logs??