Is it OK to turn off the power to a fuel furnace to replace the thermostat? Will the furnace start back up once power is restored? This is on a new furnace with an old thermostat and fuse panel.
Yes, it is fine to turn off the power, and you should. The wires going to the thermostat are low-voltage (typically 24V AC), but connecting the wrong ones can still potentially damage the control circuitry.
Most furnaces made in the last 10-20 years use electronic ignition, so there is no pilot light to worry about (if that's what you are worried about). Even with a pilot light, I don't believe it would be an issue, but at worst case you'd have to re-light the pilot.
This may be bad advise.
If all your doing is swapping out a thermostat. This is fairly low voltage. I wouldn't kill the power. After you disconnect each wire insulate it with electric tape. Once they are protected pull the wire through the hole and insert on the new thermostat. When mounted take each wire and remove the tape, then install. If your careful to keep the wires separate there will be no real danger. Even if the wires touch momentarily all it will do is be telling the furnace to fire up, It wouldn't cause any damage. I wouldn't touch the two bare wires with your tongue however.
As far as effecting the furnace it could put out your pilot light. As a precaution you may just want to shut off the pilot light and the gas before you kill the power. You would have to go through your relight procedures depending on the age of the furnace and the type of pilot light.(one that is automatic or continuous.)