Whenever I cold boot my PC, sometimes everything is fine, but mostly the graphical login screen does not appear, and screen remains grey, stuck at the point before the appearance of mouse cursor. If this happens I cant even switch to other TTY with Alt+F1 or Fn. Sometimes login screen appears but display keeps flickering and moving all over the screen, with everything distorted. In this case I can swith to text console. But if i restart x-server with Alt+Ctl+Backspace, the problem persists without change or is worse (becomes like the first case).

On a reboot or two the problem goes away and everything is normal.
What could be the problem?

I am on Debian lenny with KDE3.5 desktop.

You could try turning acpi off. I forgot what button to press at bootup, but there's a button that takes you to the bootup to select which img of linux you want to run, at that point you edit the line and add the option that turns acpi off, usually u append acpi=off.

That might solve the problem.