Thanks, Prayag! This would have been a good link if the problem had turned out being on Linux' end.
I should mention, after my first post I discovered that even the BIOS logo had some graphics disturbance, which then looked like the issue cannot be Linux.
So, in my case, as it turned out (sometimes we just have to face reality) it was the graphics card. Meanwhile I have put in a new low-end model (nvidia GeForce 8400 GS), and my machine got back to normal, without the smallest hick-up.
So, people out there, if you ever see a screen like mine, there is a big chance you must start looking for your wallet.
Last edited by jot; 10-20-2010 at 12:33 PM.