That is due to the limited color gamut of the printer who's profile you are using. You're doing it exactly right.
You can go to selective color (Image/Adjustments/Selective Color) to try and boost some of them, but if they are out of gamut, you can only do so much. A lot of printers out there have difficulty with really vivid colors, like reds, greens, and blues.
Try another printer profile, and you'll see different (but not necessarily better) results.
BTW, which lab?
Try this profile, and see if it's any different. Just for comparison, this is the lab smugmug uses:
ezprints; Right click and save file.
I'd love to hear back and see what your results are.
Here is a good calibration photo to test with.