I replaced a layer's source with an new feature class and got this error for the first time today. I tried all the suggestions on here and no success. I decided to go through all of my layers and create new feature templates and it worked.
I also got this error, and tried everything mentioned in this thread, without resolution. I finally figured it out, and thought I'd add to the comments here.
My service choked on publishing out georeferenced PDFs. As soon as I converted those PDFs to jpgs, and georeferenced them, it published without an error.