Lots of print labs print using auto corrections (brightness, contrast, color) which can ruin a lot of hard work trying to get things right in PS.
If your monitor is properly calibrated then see if they will print with all auto-corrections turned off. If they won't, find a different print lab.
Also, maybe post one of the dark images in this thread. Who knows, maybe your monitor isn't calibrated as well as you think and the brightness is turned up too high. Those of us that also use a calibration tool and get prints that properly match can give you some feedback as to what we see.
Most monitors are way too bright out of the box. When it was new I had to reduce the brightness of my Dell 2209WA to 10%, and after a year of pretty steady use I now have it at 15%. Compared to the factory setting it looks really, really dim.