Mismatched equipment.

Indoor coil probably not big enough for the newer, higher efficiency outdoor unit, causing unneeded strain on the outdoor unit. I also doubt it is charged correctly for that reason. Usually manufacturers won't honor warranties on mismatched equipment.

They absolutely should have replaced the indoor unit at the same time to get a matching system that works.

Here is some literature attached below for you to read and understand better. 10 SEER coils are too small for 13 SEER units.

Here is a link that might be useful: Carrier white paper on matching

One last thing to say. The installing dealer needs to check refrigerant charge and airflow. While the mismatch certainly isn't helping the situation, I'm not saying it's the definite cause of the freeze up. Many factors can cause this. Air filters clean?

Thanks for the replies!
Air filters are clean. I have allergies so we are hawks about making sure they are changed frequently.

You are correct, it is a 13 seer- former one was a 10 seer.

We did not change out the air handler as it is 5 years old. The coil in the old HP cracked and it was only $200 difference in price to replace the HP with a "comparable" one instead of just replacing the coil. I am frustrated that we were told the new HP would work fine with the old handler. If I had known, I would have just replaced the coil and kept the 10 seer.

I read the carrier info supplied above and am sick about the fact I have a mismatched system. We had two different companies give us quotes and none stated that we would have to change the handler. I feel misled from both companies.

The HVAC company that installed the HP will be here this afternoon so I will go over all of this with them.

You guys are great!!!! Thanks again!

HVAC people just left.
Coils inside air handler are a block of ice and refrigerant is low.
They plan on coming back tomorrow once coil is not frozen and recharge the system.
They skipped around answering about the mismatched system but said they will discuss it with their boss.
I will find out more about it tomorrow.

The HVAC person stated that as long as the HP and Air handler were the same tonnage EX. 3.5, seer was only important as an energy efficiency rating.( After the info you guys gave me ,I know this is not correct)
Also, the Air Handler has a piston rating of 72 and the HP has a piston rating of 67. It states on the air handler that the number 72 should be the same number on the HP.
The HVAC person stated that it was not important that the numbers match.
I feel as if I am fighting an uphill battle.

They are wrong. You need to find a more competent contractor, as they have no idea how to properly match equipment. SEER rating comes from the fact that a 10 SEER coil is smaller than a 13 SEER coil--the more surface area, the more efficiency. That's why the SEERs have to match, and brands should match as well. What is the brand on the indoor air handler?

If anything, the indoor coil should have a TXV and not a piston metering device. But I would not even go that route--I'd want a properly matching indoor unit to go with the new outdoor unit.

It only makes me wonder how many other corners they cut in proper installation techniques. Systems don't just need to be recharged. They leak the refrigerant out. They need to find the leak and not just "gas and go." See how the properly charged system runs and let us know. It may operate without icing up once its charged correctly (probably will). They need to find that leak though.

to clarify, ryan, you're not suggesting replacement of the complete air handler but just the (indoor) evaporator, right? (assuming a new coil will fit properly)

The coil is the major component in the air handler. Won't be a huge price jump to get a brand new, single-speed air handler, and that would also buy you a 5-10 year warranty and new blower motor, control board, etc. So I am suggesting complete replacement of the air handler if necessary to get the system working. I don't think a larger coil will fit in the air handler.

There is a chance the system will cool fine once the charge is corrected and the leak found. However, it won't be efficient, and the other issue is that since its a heat pump, when heating season comes around, the charge will almost certainly be incorrect due to the mismatch. Mismatching isn't the end of the world, but it can cause problems, especially when the indoor coil is smaller (10 SEER). It happens every day, but it's never been recommended. It looks like in this case, however, the low charge is causing the coil to freeze up. I question the responses of this company. Maybe it's a tricky install and they just didn't want to tough the indoor unit (OP: did the installers go to the indoor unit during the install?). Looks like it could be a crawlspace install.

It is an easy crawlspace install.
I am sick over this.
We chose to not change both HP and air handler as I was told by 2 different installers it was not necessary . Also, the cost seemed ridiculous as the whole system was at the time just slightly over 5 years old.( within a month past warranty)

Ryan is correct about the mismatched coil issues. And you will not be running the unit at the efficiencies as Ryan stated.

However, I believe charging the system will resolve the frost issue. I say this only because the system was replaced in January. Not having a matched system, using a charging cylinder would not have allowed for an exact charge. I would almost bet they added refrigerant until they maintained a charge that would give you heat and did not use the cylinder. To properly charge a system in that manner, the temperature has to be maintained at 75 degrees or above. The charge is critical and if it was low, which is most likely in your case, you'll get the frost. When a heat pump is designed for a home, it is initially designed according to the cooling needs of the structure.