12V-Netzgerät ist etwas zu schwach ...

du kannst versuchen einfach parallel zu 5 volt (7805 ausgang) einen kondensator mit ca 500µF beizufügen ...
denn das relais brauch es etwas mehr stromm um zu schalten, als um zu halten...

ah ... ubrigens: die schaltung http://www.b-l-w.de/serialrelay.php geht auch mit 12 Volt ... auch fast ohne "umbau" (muss man einfach nachschauen, was fur relais man hat.)

und ... mess mal den relais-widerstand ... und rechne aus, ob deine netzteil uberhaupt für die relais "ausreicht".