Just to add my report to the list in the event this becomes an issue later.
I'm in London, it's cold, iPhone 4 (iOS 4.1) is cold (not freezing just normally cold as per ambient room temp), i.e. within operational norm.
Not running any unusual Apps or doing anything on the phone.
Call comes in, rings once and then immediately gives the "Temperature - iPhone needs to cool down before you use it."
Had to hard reset it to bring it back to life.
Never seen this before. Ironic seeing I was in Ghana two weeks ago when it was proper hot and the phone worked fine.
Looks like an iOS bug to me.