Lo he probado y sigue pasandome lo mismo 
, he hecho pruebas y creo que en parte puede ser del sistema de alimentación. Lo tengo puesto con un cargador de 9V al jack de alimentación y me he fijado que a diferencia de los cargadores de 5 V normales este al desconectarlo o apagarlo corta la tensión instantáneamente y hace una especie de pico en los relés que los enciende, sin embargo con un cargador de movil de 5 v por ejemplo conectado al USB almacena cierta energia al desconectarlo y hace que no se activen las salidas de los relés al apagarse poco a poco por la acción de un condensador supongo.
Lo que también he visto es que sin siquiera tener programa las salidas del relé se me activan al meter tensión al arduino, durante un minimo instante, pero es algo que me mosquea... eso lo he visto alimentandolo tanto con la fuente de alimentación de 9V al jack de alimentación y con el cargador de movil USB a 5V.
Lo que he pensado que podria funcionar es : -en las salidas del arduino que van a los relés meterles unos condensadores intermedios para que mientras que estos no se carguen no sean capaces de encenderse los relés, si creeis que es buena idea... 1º que capacidad deberian tener esos condensadores y 2º ¿la tension?, supongo que eso dará igual siempre y cuando sea superior a 5 V la tension del condensador.
Al final parece ser que es algo mas de hardware que de software :S ...
Saludos y gracias por la ayuda 