I would say 24x36" is definitely doable on a 5D2 if the exposure is good. I have done a 20x30 print from my old, old D60 (6.2MP) as well as up to 30x40" from my old 50D (15.1MP), and that's because that's as big as mpix and some other labs would print. I have yet to make a print from my new 5D2.
When sending to the lab it's a good idea to find out the native resolution of the printer. For most, 200dpi is default. Some may go up to 300dpi if you want to retain a lot of detail. I send my files to the labs by Dimming the resolution to 200dpi but don't size to your final size. Dimming, BTW, is an old Scitex Prepress term, which in Photoshop-speak means adjusting the image size with the "Resample Image" box unchecked. The image size will adjust to the new resolution.
Most labs will tell you to leave the sizing to the imager's RIP. They can handle the interpolation better than Photoshop.