Soo, ich hab jetzt noch mal recherchiert und es kann sein, dass die Fuse Bits einfach nicht zum ATMega mit einem 16 MHz Quarz passen, da haben die Arduinoentwickler wohl Mist gebaut ...
Wenn ein 16 MHz dran ist, muss nämlich eigentlich CKSEL programmiert sein, wenn das nicht der Fall ist, sollten nur 3 - 8 MHz Quarze angeschlossen sein.
Bin also noch mal zum Elektrohandel und schnell nen 4 MHz Quarz gekauft. Ergebnis: /edit: mit dem Quarz funktioniert es! yippie! 