Finally the problem is solved.

Thing is that colleague has regional settings that differ from US
English: comma for decimal symbol and dot for digit grouping.
It appears that Rnd() return is in local format (decimal symbol -
comma!!!), while Cells(x,y) = or Cells(x,y).Formula expects formula to
be entered in US English.

The solution is simple: add .FormulaLocal where applicable :)

BTW Previous solution with WorksheetFunction.RandBetween also didn't
work. I was misinformed by my colleague.

Hope this will be useful.

Regards,
Shahin