I got the message on my iphone 4 sitting on my end table in a 73 degree room with the phone laying on the table (not being used) and was cool to the touch. Got a call, the message popped up and the call went to vm. Will be calling Apple tomorrow on this issue.
from iPhone4s page on Apples site
I would expect that "Environmental" means it should be operable up to 112F ambient air temperature, not the actual device temperature (which it appears apple should have said something like "Nonoperating temperature: below -4F and above 113F)