I'm having some of the same issues, but mine stem from trying to publish a 10.1 map to be able to be read by 10.0 arcreader...
My boss suggested to "Save a Copy" of the 10.x MXD in the needed version (you can go as far back as 8.3 when saving). Then open that MXD you just created. Try publishing it again. I don't know if this works yet, as our EMC hasn't gotten back to me yet, but ideally it should because you have a 10.0 mxd... I'll let you know if I figure anything out...