Just upgraded from 10.6.1 to 10.9.1. Everything worked fine except I could not publish hosted layers and publishing registered data worked but gave an error.
Had the same errors as you did in my logs.
So I did what you suggested, as well as increased the max number of services and max timeout (the update flagged them as too low), for the publishing services and now everything works!
Thanks for posting this question and especially posting your solution!
#CLE #sloth