Debian server freezes at random times until key is pressed

When booting my personal code server (Debian Squeeze), the boot screen freezes almost immediately, but when I press a random key (including useless keys such as NumLock) the boot process continues. This happens several times during boot - a random process will stop, continuing only after I press a key.

Once GDM shows up (requiring at least another key press) and I log in, the mouse changes to the "waiting" icon, stopping a couple times until Gnome starts up - from then on, the computer works normally... unless I try to switch to/from a console, in which case I have to (yeah, you guessed it) press a key. This also happens while using gnome-terminal (extra diagnosis: if I try cat /proc/cpuinfo, for instance, the command will hang the first time, but after that it will work flawlessly). This also happens when logging through ssh - if I issue a command on my netbook, and press any key on the server keyboard, the command will get unfrozen immediately.

Finally, this happens too when shutting down the computer (it will show something as "Shutting down Samba", but it continues only after I press a key).

Any ideas about why could this be happening?

Important detail: Sometimes if I don't press any key, after about 15 seconds the system continues doing whatever it was trying to do at the moment (particularly noticeable through ssh, when I'm not near the keyboard and, thus, have no alternative but waiting). This would also explain why Gnome is not as fast as it should (slight delays showing menus, switching programs, and so on).

Extra info:

• The computer has a 2.6.32-5-amd64 kernel.
• The video card is an ATI Radeon, but the problem was present both before and after configuring xorg.conf to properly recognize it. Both the video card and the motherboard are Gigabyte.
• The keyboard is PS/2 (I tried another PS/2 keyboard with no success, and I don't have any USB keyboard available). Plus, ...
• The computer works fine under Windows XP (32 bits).