Spectrum has it right. The issue of the air temp being above or below freezing is more or less irrelevent other than that "warmer" air will rewarm the pre-breathed first stage slightly faster. With enough gas flow, you can chill a first stage below freezing even in mid summer.
I think you need to look at it as a checking account. You only have so much money in the account to work with and you only get paid every so often. So if you "spend" your money too fast, you are going to overdraft.
Applying this to a regulator, the reg is going to cool a certain amount during pre-breathing due to adibatic cooling caused by the expanding air needing to draw energy (in the form of heat from the environment) to provide the extra energy needed for expansion. This cooling effect is more or less cumulative above water where transfer of heat from the relatively warm environment is minimal due to the poor heat tranfer traits of air. This is especially true in cold air close to freezing where there is less temperature differential in the first place.
So..if you pre-breathe, the reg will be colder when it enters the water. If it is below freezing, the potential exists for water to freeze inside the ambient chamber where it can impede the movement of the piston or diapgram causing a freeflow. Since you will also breathe off the reg under water it will continue to experience adibatic cooling and even the greater heat transfer traits of the water may not be sufficient (in very cold water) to get the temp back above freezing inside the reg and that small amount of ice in the reg can continue to grow during the dive causing a freeze fllow later in the dive. The colder the water, the less heat available for heat transfer and the greater the risk of this occurring.
So if diving in very cold water and in cold air temps, it's still a bad idea to prebreathe your reg unless it is extremely freeze resistant (ie: a fully sealed ambient chamber). What is worse, some divers not only pre-breathe their regs to test them, but also use the power inflator to fill the BC and inflate their dry suit prior to hopping in - and then blame the reg when it freezes up. Many divers get away with it for a long time, but given enough gas flow prior to the dive, cold enough air temps, and cold enough water temps, a freeze flow is in many cases inevitable.
I also agree exhaling in the second stage is a bad idea in cold weather as the moisture in your exhaled air can freeze inside the air barrel, poppet, etc. and lead to a freeflow. This is especally true with second stages with plastic cases and plastic air barrels as they are essentially insulators that impede heat transfer.
Personally, I feel you should test your reg at home and trust that it will still work an hour or two later at the dive site. I'd also recoomend orally inflating your BC. prior to a very cold water dive in cold air temps or alternatively fill it off another tank and reg that will not be used on the dive.