Non-precision instrument approaches generally have altitude restrictions which get lower when you get closer to the airport. I always figured these restrictions were AMSL using the current altimeter setting, not compensating for temperature.
Some have heard the mnemonic that mountains are higher come wintertime, which basically means that colder weather make your altimeter read higher than you actually are (or, as most pilots prefer to think, you're lower than what your altimeter reads)
Have a look at this VOR approach into Newark
Most altitude restrictions are a minimum level, so you're free to fly higher if it's a particularly cold day. But have a look at LOCKI intersection, the final approach fix. That's at 1500 ft, not at-or-above. At -40, this will put you around 1100 ft above ground level. Although I don't see any obstructions that high during this segment of the approach, as far as I know instrument approaches are supposed to guarantee a 500 ft obstacle clearance, do procedures using this kind of restrictions have a minimum temperature?