Hi,
Does your relay just not open at all sometimes or can you hear it clicking a lot as it continuously opens and closes?
Its not 100% necessarry to use a capacitor on a relay, although it can help with decoupling/ smoothing signal.
If youre using the same batteries for the relay coil as the circuit,then when the relay switch closes, the circuit may drain the batteries too much and therefore open the relay again.
Also check the batteries / required ratings etc...
Also youre relays could be damaged if the coils have over heated due to over powering them...