How old are your windows? Are they tight and do they have double panes of glass? The windows are a big source of leakage. This may be part of the problem.

Have you tried raising the thermostat to 72 degrees? There may be some temperature vairations in your house. You may have to raise the thermostat a degree or two to compentstate for this.

When you said 'walls are cool to the touch', that is not good. need to buy a temperature gun (around $50) and go around the house, check all walls, ceiling, floor and find the cold spots, so that you know where to add the insulation.

It is a one story, with an attic and a crawl space.

prior to insulation air sealing should be done.
insulation doesn't stop air flow..except foam insulation
when correctly installed. as air moves through the
insulation it robs the insulation of its R-value.

since you can't air seal now in the attic..because
they have insulated it..your only option is to
air seal from inside the house.

can you explain this a little more clearly?
"So, they pulled out the batting in the new part, and injected some spray foam."
where did the inject spray foam? did they have
a foam rig or cans, or package foam kit?

any insulation in the floors?
I have a crawlspace. in the winter the floors
are frigid. two pairs of socks, slippers feet
cold all the time. I'm going to foam insulate
my floors. 3" of closed cell will give me R-21
and air seal.

conventional insulation doesnt work in open crawlspaces.
as the air blows across the insulation..it robs it
of its insulating value, much like in the attic @
air leakage sites.

old insulation still retains its R-value unless it
is torn or flattened. that the company couldn't determine
that there was insulation in the walls..that isn't a
good sign.
I'd shop around for another company if you chose
to do more.

in my house..it was the air leakage of the house that
contributed to it being so cold in the winter.
as I've sealed off leakage..house is warmer.
I've probably blower door tested my house half
a dozen times over the years. as large leakage areas
are sealed, then smaller leakage areas become
apparent. of course, I have the equipment..so its
not a big deal for me to test.

if you invest in a blower door test..it will show
you where the leaks are. then you can address the
leakage and improve the comfort of the house.

you mention nothing about your hvac system.
how are you heating and cooling the house?
where is the ductwork..attic...crawlspace?

more info will help us to help you.

btw..40 degrees! brrrr its sunny & 80 degrees
here today..its been a yardwork day!

best of luck.

melynn- Yours is a somewhat puzzling story, but let me ask this - if you're outside on a mild day (not in the sun) and it's 70 degrees, are you very cold? Could it be a humidity problem inside (cold and damp?)? Had it been raining outside when you felt so cold?

Energy, not everyone agrees spray foam is the greatest thing since sliced bread. Some say they perceive and are sensitive to off-gassing, who knows? Petrochemical foam anywhere within a structure presents a great danger in the case of fire.

In my mild weather and uber eco-conscious region, spray foam isn't used frequently (to my knowledge) and doesn't have a strongly favorable reputation. I'm sure regional and climate differences offer other answers.

I've never said foam was the greatest thing
since sliced bread. if you read my posts
the only places I recommend foam is roofline
when ducts & equipment is in attic
and floors over crawlspaces.

in op's case..if the foam offgassed..which
in most cases offgassing is a symptom of
componets mixed wrong..if she installed
foam to undersides of floors over
a crawlspace..it would offgas to ambient.

foam may not be a common install in your
area, or perhaps you are not aware of installs
in your area. either case, foam is a widely
used insulation.

it has long been my pov that foam is a cover
for bad building practices. that the homeowner
has to spend 3x the cost to both air seal and
insulate speaks loudly to the trades who make
all the holes in building envelopes.
but when weighing the time, effort and materials
to air seal..homeowners often opt for an
insulation that both air seals and insulates.
economically and to labor intensive time
to seal these difficult to work in areas.

granted this is based on my years in the
trades,inspecting & testing homes & installs.
not just the trend of the day.

have a good weekend.

I read your comment as a quasi recommendation - I work in this industry, and here's what I'm going to do with my house.

A couple of years ago, I decided to upgrade my attic insulation. I had out the area's largest insulation contractor for a bid. I asked if they did spray foam, the answer was "Yes but I don't recommend it". I asked why, he said "In this area it's not a good investment, too expensive and the payback period is too long. We do it mostly for buildings looking for one green designation or another".

I thought I was clear that my comment was based on what I know about my area - isn't that where most comments come from, yours included? This was based on discussions with people I know (including builders) and my discussion with this insulation contractor. I don't question your expertise, nor the applicability of foam in areas with extreme weather. Maybe OP lives in Minnesota, or maybe in San Diego, only know that wherever she is, she'd like to be warmer.

If the house is 70 and you feel cold lets stick to the basics.
1) Get a home energy audit (blower test) and then caulk / insulate were necessary. I'll bet you use less energy ($) this year and are more comfortable.
2) if your windows are old and drafty you may need to think about replacing them. I've done replacement windows and have been as snug as a bug in a rug. Mine are triple pane.
3) I had several inches of insulation blown into my attic. The house is very comfortable.

My kitchen wasn't properly insulated and was freezing in the winter. I insullated and put a yotul gas stove back there in the attached den. It was so effective I bought another for the front of the house. They heat the entire house and the heat is in the room with you. Its running now and it's really toasty.

I'm puzzled. My house thermostat is set at 61. I'd be in trouble if 70 felt cold. Interior humidity might be the only explanation?