Shawn,
If they are working in very cold air temperatures, then newly-exposed subsoils will cool off overnight. However, they should not be capable of freezing to any significant depth.
If his equipment has sufficient break-out strength to get through your existing frozen soil, then overnight freezing will be no problem.
If your contractor is capable of excavating to START your project in winter, then it should not be a problem to finish excavating. I think many of the replies you received were from people worried about getting proper compaction (if needed) for a pond created during winter.
