.mxd was a red herring. Disregard
Ok I found my problem. Maybe it relates to yours. I was storing my locator in the sde database. I just rebuilt and tested by simply storing it in a web accessible folder and all is well, successfully rebuilt and was able to generate a service from it.
You might try storing your locator in a different place and retrying your script based method.
Thanks for the help.