Digital BW, The Print

Probably not your same problem, but I suffered "mottling" lack of 
smooth tone transitions when I first started out and was testing 
various printer profiles and rendering intents. It was a big problem 
with profiles I created using Monaco's software. Images were fine on 
screen, lousy on paper. When converted to grayscale, tone transitions 
prnted smooth. I assumed the problem was due to poor conversion of 
image data to workspace by the profile/driver combo. Not apparent on 
low saturation images, but apparent on most normal color images.

I went with ImagePrint and all such problems disappeared and I never 
looked back. Suggest you try a different profile, or lower 
saturation, maybe all the way to grayscale, as a test. If the problem 
goes away, I think it's good evidence of a profile problem.