New Cold Weather Issue

[teamdaemon at comcast.net]

So, now that the heater control valve is fixed and everyhting is happy there, a new issue has popped up.  Now, when the car is cold, as in first thing in the morning or after the car has sat all day in the parking garage, the starter is hard to engage.

Turn the key - starter just spins, does not turn over engine. Stop.  Try again.  Same thing. Try again, engine turns over a few times, then starter spins free. Finally, engine spins up and car starts.

Once the car is warm, doesn't seem to be an issue, car starts right up, no fuss, no muss.

Thoughts? Is the bendix gear on the starter just freeezing up and not engaging?  Fix?

TIA,
--
Paul