Aperture 3 Lab Printing Help

[Mooregame24]

I tried printing a large photo of mine to an online lab and was pretty unhappy with the color results. Greens appear blue, very dark, etc. So I've been trying to research all I can to prevent this next time.

I've used Spyder3 Pro to calibrate my iMac, installed the icc profile the lab provided and have that profile selected for onscreen proofing. Viewing the same image using the new settings doesnt change it much. Certainly not to the degree of the print version. Where I get confused is how to properly export the file so it's ready to print in aperture. Can someone explain this workflow to me? I get the 'export version' command but I've read that you may need to imbed the profile, etc. but this is where I get lost. I just want the prints to match the screen when I send it to the lab!

Thanks in advance for any help. This color management is throwing me off.