** This issue has been resolved in ArcGIS 9.0. **
The ArcMap document that users want to serve contains a layer that references a GIF or LZW compressed TIFF data. When attempting to serve this map, the following message displays:
"Error when trying to administer mapservice. Service 'service name' cannot be created. Data for the layer 'layer name' of 'data frame ID' is not found."
This is a known issue.
Solution or Workaround
Convert the raster data to a type other than GIF or compressed TIFF that does not rely on the LZW license. Having the layer refer to this data, instead of the GIF or LZW compressed TIFF, allows serving the ArcMap document using ArcMap Server.