I was just struggling with this topic and stumbled upon another gotcha ... thought I'd pitch in my $0.02. When publishing a map service, make sure you enable "Allow per request modification of layer order and symbology". This can be found in Service Editor -> Capabilities -> Mapping.