"No, there is nothing in BIOS."
"The problem is that when I turn the computer on, the monitor sometimes stays black!
I have to restart 2-3 times to get it on, once the monitor is turned on it stays on - no problems at all. (I restart before grub loads, it has nothing to do with any OS.)
BUt why doesn't it "wake up" directly?
Strange is, if I boot the computer and monitor stays off, it doesn't help to connect my old monitor instead. No signal! If I boot without monitor I can connect my old monitor just fine."
My next guess is that there is an intermittent error in the power saving feature in your new monitor. Try turning off the monitor's power saving feature so that it never tries to save power when the CPU does not contact the monitor for a set period of time.
If possible try an identical Fujitsu monitor to see if the problem happens to be a defect in the one particular monitor that you bought. Is it still under warrenty?
Be prepared. Create a LifeBoat CD.