Newb mistake: after updating anything in the mxd and republishing it to your server, always remember to copy over your new/updated data.
Oddly, ArcGIS Server manager doesn't seem to complain much if a layer's data is present on your local environment, but isn't yet up on the server.
All the log file says is " WARNING The Layer:'***' in Map: '***' is invalid.
Good luck,
James