Tengo el mismo problema, y creo que tengo la solucion aunque aun no lo he probado,
tienes conectado un diodo a la patilla de enmedio del transistor? Por lo visto esto evite que al activarse la bobina del rele la corriente vuelva en el otro sentido y provoque lecturas erroneas.
http://www.arduino.cc/es_old/Tutoriales/Rele
Es el 1N4001, creo, ya me diras algo.