When a layer is labeled, the map service publishing preview is empty on Windows 2003 terminal service in Application mode; no labels or terminal service set to adminstrative mode, and the preview is fine.
Turn off the labels or set the terminal service to use administrative mode instead of application mode or @esriBGLfntmap.dat file from one machine to the other.