[syhprum (OP)]

Walking on water was described as miraculous by early Christians it is no great problem when temperature's are low is there any evidence for abnormally cold winters in the middle East round about 30 AD ?   

[CliffordK]

Some people fake walking (or driving) on water by putting a platform covered by a thin layer of water, to make it look like it part of the lake or body of water.  Perhaps this could also occur with natural rock formations. 

However, trickery aside, your assumption of ice would not be too outlandish, especially in a locale where ice was rare, and with little international communication.

I believe that the mountains of Afghanistan get to be quite cold in the winter.

Every century or so, there is a volcanic eruption that causes significant climatic disturbances.  For example the 1816 eruption of Mt Tambora presumably caused http://en.wikipedia.org/wiki/Year_Without_a_Summer [Links inactive - To make links active and clickable, login or click here to register] (which also caused significant winter disturbances).  Is it possible that a large volcanic eruption in the last 10,000 years caused a particularly memorable climate catastrophe in Northern Africa?

Perhaps one should not underestimate the impact of international trade.
Consider a person living in a place with no frozen winters.  No refrigeration.  Really never seen ice.  Perhaps not even hail.
Then, a trader comes to town with a story.  Across the sea, there is a mythical land where it is so cold in the winter, the rain comes down like a layer of white sand.  And, lakes become so hard, one can even walk on the lake. 

A few generations later, such a story could truly take on mythical proportions.