Somehow, the portable CD-ROM we always had here at work has disappeared so I had to use a USB stick to try to re-install one of our machines. Downloaded the really great UNetbootin, installed Debian, went over to the server room, enabled USB booting and what did I get?
SYSLINUX 3.85 2010-02-20 EBIOS Load error – Boot error
Pressed enter – nothing. Okay, back to the office, searched a bit around, found out I should have maybe tried to boot with qemu: qemu -hda /dev/sdb1, works like a charm, weird. More searching but nothing conclusive, so I formatted the USB stick to FAT32, installed Debian again, went over, plugged it in – nothing new. Crap, especially as I am pretty sure that I booted another machine with that stick before. So back again, plugged it into my old laptop – same error. I finally changed to another USB stick (different make and model) which I luckily had with me (after reading this thread) and, tada, it finally worked. So: if you get the same error, try first with another USB stick before reformatting etc.