Jeff, Yes, my display is indeed calibrated & profiled. (In fact, it is calibrated to ProDPI's recommended standards).
That may be your first problem! They may think it's a calibrated standard (it's really not). If the calibration targets (aim points) are not such they produce a visual match under a good illuminant viewing booth next to the display, the values are wrong, you are not calibrated. See: http://www.luminous-landscape.com/tutorials/why_are_my_prints_too_dark.shtml
Did they allow you to use the profile they sent to convert the data? If not, if they demanded say sRGB, we have no idea if the profile they provided for soft proofing was indeed used by the lab. Had they allowed you to use it, you'd be able to pick a rendering intent you prefer and they would have to send the RGB values, in that output space to the printer. But the printer may have changed behavior due to less than ideal process control. The profile you have may not reflect the output.
ICC output profiles have two important tables to do their job. The preview table in the profile may not be in sync with the output table in profile. What you see isn't what you get.
As Jeff points out, the viewing conditions play a huge role in what you see. Hence the silliness of someone specifically recommending display calibration settings without knowing about the type of display you use, how you view your prints, etc.