Lo cierto es que todo eso ya lo probé. Comprobé que el puerto fuera el correcto, que la placa esta bien seleccionada en el menu tools>Board, instalé el propio paquete que trae los repositorios de fedora para arduino, probé a reinstlar la IDE y probé también con las dos versiones del IDE para linux de 64bits que encontré. Incluso lo intenté en otro ordenador de 32bits y con windows por si fuera ese el problema pero nada, el problema persiste.
El caso es que cuando he trabajado con otras placas (placas nano, duemilanove y arduclema) nunca tuve este problema ni nada que se le parezca y como el arduino UNO es la versión más reciente y cambiaron el chip del serial pensé que quizás ahora si era necesario poner el Serial.begin para trabajar con los delay. Sin embargo ya veo que no, que el problema esta en mi placa o en el ATMEGA328.
Finalmente creo que probaré a actualizar el firmware del ATMEGA 8U2 y si sigue igual probaré con otro ATMEGA328 (creo que es lo que me queda por probar, el firmware y el cambiar el microcontrolador). Si no se da solucionado tendré que apañarme con 12 pines digitales cuando use los delay o el puerto serial, que remedio...
Si alguien tiene alguna idea más que comente a ver si se soluciona.
Gracias a todos por la ayuda.