Well, I didn't try to Arduino NG on the other box, but I guess that's the clincher. Since the board didn't work on the other computer (different OS as well), it must be down to the chip or some other component on the Arduino.
I think I'll try to solder a more reliable programmer (with a plug) some time this week and attempt to program the bootloader again. I'll let you know how it works out.
Cheers again,
Jonas