Unless you work closely with a third party printer all your calibration is,
sadly, for naught.
The best a distant and reliable third party printer can do is arbitrarily
find a neutral gray in the image (or some analagous landmark) as a reference
point for their own color managed printing system.
If your printing service does not even bother to do that you need a new
printing service.
Better: learn to print your own using color management.

You will have to ask the lab. It's likely that they can't handle Adobe
RGB and/or they are allowing further automatic adjustments.

Pablo,

Adobe RGB and sRGB (the "Default") are what are termed "device dependant"
profiles - the results you get depend on the device that generate them (as
opposed to CIE LAB which is device independant). Perhaps a good analogy
would be with map directions that say "take 20 paces to the north, then 45
paces east - then start digging" - where you end up depends totally on how
long your paces are. Same with RGB - it defines how much R  G  and B  to
use, but doesn't define just what shade the Reds, Greens, and Blues are.
Correct colour management attaches profiles to your RGB data that
effectively says "when the map maker took a pace it was 3 feet long - so if
your pace is longer then it knows to tell you to take less paces".

In your case it's most likely that you're feeding the lab Adobe RGB, but
they're treating it as sRGB - which means that everything will look a LOT
darker. If that's not the case, then we've definately got a more serious
colour management issue. Try sending them a small sample in sRGB - also
check with them as to what colourspaces they can handle. See also if they
can hadle a file that's in LAB colour - if they can, and it's still wrong
then you've most likely still got a monitor calibration issue.

You said that your monitor has been calibrated - was this with a
Colorimeter, or just using AdobeGamma?

Cheers,

Colin

PS: If you're keen, pick up a copy of "Real World Color Management" 2nd
Edition - it's the current definitive text on the subject.

It depends on the lab.  Many don't handle color profiles at all, so you
must convert to sRGB to send the pictures to them.  You need to find out
how the particular lab works.

The color profile they send you is for -soft proofing- the image in
photoshop. My guess about the problem is they are expecting the file in
sRGB and their software doesn't do a conversion from aRGB to sRGB if you
send them aRGB files.

DON'T convert the file to their printer profile before you send it to them!
That isn't what the profile is for. 99% of their customers don't know what
a profile is, don't own photoshop and use an sRGB P&S that doesn't tag the
files, that's what they expect. You threw them a curve ball with the aRGB
files. You can use their profile to soft proof and mainly to look for out
of gamut colors in your files and correct them before you send the sRGB
file.

Cool shots.

what are you doing now to fix your images?

are you setting levels your self or using auto levels?  you can learn to set
your own white and black points.

you can burn and dodge your images, you can render one for the highlights, a
second for the shadow areas, layer them and erase or mask this area and that
for the best of both sides.

but if you are having problems with a local printer, tell them to turn off
any auto exposure or color and contrast adjustments they may do to 'help'
you.   the average consumer just takes the chip out of the camera and puts
into the minilab's terminal.  Have you ever seen their histograms?  a hump
in the middle with nothing at either end, no wonder the amatuer labs
automatically add contrast.    If I forget to tell the clerk at the lab to
turn it off I get something back that looks fried, if they turn it off I get
just what I want.