Care to post your original soft copy and a scanned copy for comparison? I might due to your setting in your camera. What's the resolution you were shooting at? For 4R, minimum 1200 x 1800 is required. If your photos' reso is lower than that? You need a digital artist instead of the printer to correct the prints.
I was shooting with a D70 at jpg/large/ fine setting, the same setting as what I use for my weddings/PR/events/etc.
I'm not too sure about the 1200X1800 for 4R thingy, all I know is that, except min setting ( as I've never done that before ) so far I've no problem with whatever setting used when I sent to my normal lab.
Anyway, the problem is with the tone and colours. Res. size will not affect this too much unless it is in the extreams. Small file size will affect the pixels and colour bending first but there were no issues with that.