Michael,
You can't publish a mosaic dataset in a map service without the Image Server Extension. 😉
Shaun,
As for the black/white checkerboard, this indicates the imagery could not be found by the server. Since it happens when you zoom in, it sounds like the server has access to only the overviews, but not the source imagery. Do you have the source directory registered with the server's data store and did it validate? While we're at it, since you do have the extension, what happens if you publish the mosaic dataset as an image service rather than a map service? Do you still see the issue with image service?
Best,
Eric