Solved! Go to Solution.
You may be running into a bug.
NIM087311: "Map labels do not work in a map service if the feature class resides in an ArcSDE database and is joined to a table."
This bug is listed as resolved in version 10.2.
Documented workaround: Publish a map service using ArcMap 10.1 with no service pack to ArcGIS Server 10.1 SP1.