What CMYK profile are you using for this?
Can you show a side by side screenshot?
Photoshop 4 default CMYK is obsolete and completely irrelevant today. It isn't used anywhere and hasn't been for years and years.
What you need to do is ask the printer what CMYK profile they want.
Standards vary in different regions around the world. Here in the EU region, for instance, most presses are calibrated to ISO standards and the preferred profile for coated stock is usually ISO Coated v2 300% (ECI). But no guarantees - some printers want Coated FOGRA39, and for uncoated stock there are yet other profiles.
In other parts of the world, different standards apply. Always ask!
Hmn...if it is obsolete, then why is it Photoshop CC's default CMYK colorspace?
I'll check with my printer and see what they use.
"Photoshop 4 default CMYK" is not the current default. That's US Web Coated (SWOP) v2.
And that's only because there has to be some default. The SWOP standards generally apply in North and South America - but nowhere else. Since Adobe is an American company that's the one they picked.
Photoshop 4 default CMYK hasn't been valid since Photoshop 4.0 way back in...1996. That's a long time ago, long before modern color management.
In North America you are pretty safe using the Gracol profile.