Hi Mike,
I don't use KML in any of my services, but it looks like you are running into the issue described here: http://resources.arcgis.com/en/help/main/10.1/index.html#//00sq000000r9000000
It appears that ArcGIS doesn't support halos (backgrounds) for KML layers. Unless someone has found a workaround you might be stuck using a standard label with the KML. You could always convert the KML to a feature class before publishing and your labels will come through just fine.
Matt
Unfortunately my labels are dynamic and generated by our vehicle tracking data. We change label and add a time stamp if a vehicle has not reported in for a particular duration or if other events occur.