I'm assuming you remove the resistor when using the relay - the most likely cause of the problem is the relay demands more current than the 555 can supply. It is also possible that your relay has polarized coil connections because it has an internal diode across the coil pins. If that is the case, try reversing the connections to the coil. Other than that, try adding a transistor driver stage between the 555 output and the relay to increase it's current capability.
Brian.