What you need to understand is that this is not just you. Those yellows and greens are completely unprintable. They'll appear dark and different on every screen, and in every print. This is not a problem for you alone.
The way we get around this is by soft-proofing. And to do that, the lab needs to provide you with the profile file. If the lab can't do that, they're not professional enough.