Richard, do you want to replace the entire air handler and condensing unit, or just the coil and compressor. Apologies, not sure per the way you worded it.
13 SEER is now the minimum rating that must be installed (unless you find someone who actually has a 10 or 12 SEER unit left, but then I've found that they will "bend you over" because they are the only ones who have one left).
If your unit is indeed a Coleman, not sure per the model numbers you listed, however a guess would lead me to believe that you don't have a 13 SEER unit that you're having issues with.
If you have a 10 SEER indoor coil and want to change just the outdoor unit, you MUST change both the outdoor and indoor unit to 13 SEER if you want them to work properly, and in most cases, stay under the manufacturers wrty.
I should also note that is only my opinion that you should have an ARI manufacturers "matched" system install at the same time (which means both the indoor and outdoor unit come from the same manufacturer, that is rated by the manufacturer).
A compressor changeout can get expensive just for the labor even if the compressor is still under wrty.
Air handlers? Depending on the location, labor can get up there as well. My uspstairs system was a PAIN in the butt. No way I could do it myself, I did it "above" board and got "legal" help. Complete system changeout, 56 man hour labors. If I had a couple of buddies help me, they wouldn't of been my friends after the job would of been done. Keep in mind, due to the 13 SEER being the minimum now, coil surface area has increased, meaning that with some of the manufacturers indoor lines, the equipment has gotten bigger. Perhaps not a problem, however, for myself, I only had 14" in width to get the equipment into the attic without cutting into the ceiling. Made it interesting. I also miss "up north" where everything is in the basement in an upflow configuration where you have lots of room to work.
That said, since you were able to have both systems replaced about the same time, I'm assuming there was no PITA work that needs to be done.
Depending on the BTU's of the system, you may have to change your lineset size (because of the SEER rating or manufacturer), which could be a pain in the butt as well (yes, LONG story, I went from 3/8"X3/4" to 1/2"X7/8", but this was a VERY long run, and for you HVAC guys out there, the liquid line was per the manufacturers engineering sp? department that I doubled checked with, it was correct).
With the pricing of copper, I almost fell over dead when I looked to see what I had to pay just for the lineset for my job. I already paid for my downstairs lineset a couple of months ago (that system will need to be replaced in a couple of years or so) because copper just keeps going through the roof (from a year or so ago, I'd guess by at least 50%).
I'd also look to go to a R410A system. R-22 just had one of the BIGGEST price increases that I've ever seen (we're talking like over 30%!, all you guys out there, I'd call if you haven't). Give it a couple of years, R410A will be less than R-22.
EDIT, after doing the math, at least from one major manufacturer, the price increase on R22 will be more than 30% easily.
http://members.cox.net/jamesmcalm/Calm_Domanski-R-22_Replacement_Status-EcoLibrium-2004.pdf