Thank you for the advice.
We had Windows domain security at a GIS machine level and we've had pretty average performance compared to our development box that has internal arcgis security.
There was no real need for domain security. Overnight we've gone back to internal arcgis security and publishing is now working and the rest interface is running much better.
Possibly this could be caused by a slow domain server (and that wouldn't suprise me), but I've read on the forums about some slow performance under 10.1 (and it maybe 10.2) when using domain security.