Gino, are you using a canned profile or custom one made in house?
I'd be shocked it this wasn't a profile/color management problem entirely. Grays are hard to print because your RIP sees that color and reinterprets the CMYK values so it prints what it thinks you're expecting (that's an extreme oversimplification). Poor quality profiles (and often most canned profiles downloaded from a media manufacturer) tend to shove colors a little too far one way or the other in hopes of delivering "pleasant" colors. This is probably never noticed on most spot colors or photographic images because they are still color. But with gray, your eye very easily detects when it has a color cast and loses neutrality.
Your printer has to print the gray as a combination of CMYK ink, and a poor profile is simply adding too much of one or more colors in an attempt to neutralize or balance those process colors into a pleasing gray, which results in usually a green or magenta color cast.
The only way to eliminate the issue is with a better profile unfortunately. You can minimize it somewhat with moving away from a canned profile by manually tweaking colors in your file and RIP until you squeeze out a gray you can live with, but that's highly inefficient, expensive, and not repeatable. Assuming your file is built properly with a correct neutral gray color specified, a good profile will do its job.
On the subject of the file, for a profile to print a neutral gray, you must give it a file with neutral gray. Make sure you numbers are correct, ALWAYS check the numbers. If you're designing in CMYK and you're shooting for gray and on screen it looks goo but your numbers are something like 36/42/45/67 that is not neutral. In CMYK, you should never have any cyan , magenta, or yellow in the mix. 0/0/0/50 is neutral gray an a good profile will interpret and print that accurately. For RGB, gray is just as easy, contrary to what a lot of people believe, all 3 values have to be the same. So 150/139/161 make look OK on screen but it is not balanced and neutral. 140/140/140 is neutral gray and again a good profile will render that as such.
And don't forget your icc profiles and rendering intents in the file, that will affect it as well, although not as drastically. If the file is set to relative colorimetric with the sRGB profile and your profile is set to absolute colorimetric with the Apple RGB profile the RIP will tweak colors a little off target.
Lastly, as has already been discussed, laminate can shift the color. Although with very good profiles that print neutral grays accurately, the shift is minimal, if noticeable at all. If the laminate has a yellow tint and the gray printed with a little excess cyan (which can look deceivingly neutral on its own, especially indoors under cooler colored fluorescent lighting), the laminate can add enough yellow to the mix to turn the gray green under the right lighting conditions (higher up the scale, or natural sunlight). Sometimes it's recommended to profile specific media with the laminate on it so the spectrophotometer can get a more accurate reading of the color through the laminate.
When all is said and done your problem more than likely boils down to color management. We (and a lot of other people) used to fight this daily and I dreaded any job that had gray in it. We finally in dated heavily in profiling and color management training, profiled to Gracol G7 spec and have not had a single gray issue since. Or any color issues. But it all starts with the file, if your colors are not accurately specified in the design, you're screwed from the get go. No color management system, regardless of how good, can correct mistakes the designer made because he didn't understand how to set up a proper neutral gray or rich black or blue.
