...my guess is you changed drive letters from the original.....that's why it worked before. But my guess, is you already figured that out. If the datasource was ok when you published, it was ok until you changed the MXD and republished.
FYI - I too am starting to use UNC for all my data connections....helps when switching between machines/users that have it mapped to different letters.