Vale, empiezo a entender el diseño de la alimentación de tu circuito: tienes una única fuente con la que alimentas, por un lado el ventilador, y por otro la placa del arduino.
El arduino lleva un rectificador lineal 7810 ... y supongo que algo más para alimentar el microcontrolador, no?
Yo apostaría que tienes un problema de rizado (ripple) en la fuente de 12V introducido por el ventilador, porque su tensión y potencia (la de la fuente) es demasiado baja para alimentar todo.
Te apuesto lo que quieras a que si usas una fuente de 15V de la suficiente potencia te desaparecen los problemas XD
Pero intentaré explicarme:
Al encenderse el motor, la fuente de 12V tiene que dar más corriente, lo que va a hacer que su tensión de salida baje un poco debido a la caída que se produce en su resistencia interna (menor potencia, mayor resistencia interna, más o menos ...). Esto es malo, pero no es el mayor problema. El problema también está en que el motor va a incrementar el rizado de la fuente, haciendo que la tensión mínima baje aún más.
Aquí tienen unos dibujitos muy chulos que lo explican muy bien: DC Motors -- motor (mis)behavior
O sea, que ahora tienes una fuente con más rizado y una tensión mínima más baja que cuando el motor estaba apagado.
Añádele a esto que si la alimentación de la placa del arduino pasa por un diodo seguido de un 7810, la caída de tensión mínima que se produce en ese circuito va a ser de unos 0,7 del diodo más una caida típica en el regulador lineal 7810 de 1,5V, es decir, que la caída mínima en tu entrada es de 2 voltios y pico, y, según parece, no tienes suficiente margen de tensión en la entrada como para eliminar el rizado que produce el ventilador. (Por cierto, qué diodo es, podría ser un schottky de 0,2V).
De hecho, la tensión mínima de alimentación del 7810 según recomendaciones del fabricante es de 12,5V (http://www.ti.com/lit/ds/symlink/ua7810.pdf), 13,2V si tienes en cuenta el diodo, o sea, aún más alta de lo que realmente tienes (aunque es más bien para cuando te acercas a 1A). Hablamos de la tensión mínima, no de la tensión media o RMS, que es lo que puedes medir con un polímetro.
Para poder mirar bien la señal de alimentación necesitarías más bien un osciloscopio (asumiendo un motor DC de 3 polos, y unas 2000 RPM, puedes tener un rizado de unos 12 Khz ... ; eso no lo puedes ver con un polímetro).
Bueno, yendo al caso práctico, posibles soluciones:
1.- prueba con una fuente de al menos 2V más de tensión y más potencia ... creo que se te ha quedado un poco corta.
2.- añádele un condensador cerámico tan cerca como puedas de los bornes del ventilador para eliminar transitorios, digamos de 1 nF ..
3.- aísla la alimentación del ventilador usando una bobina pqueñita (o choke, como decía fm ) en serie en el positivo y un condensador electrolítico en paralelo (este no es para los transitorios, como el anterior).
4.- añade más condensadores de filtrado a la salida de la fuente para reducir el rizado (de 2200uF para arriba).
Estos son comentarios generales que buscan disminuir el rizado y los transitorios que se comunican por la alimentación.
No te puedo asegurar que funcionen, pero son fáciles de probar, así que espero que tengas suerte ...
Suerte.