When you have your MXD open right click in the data frame and go to the general tab. From there look down at the bottom of the tab and check the box for "Allow assignment of unique ID's for map service publishing" That should take care of your issue.
... View more