You have proved once again, always using decoupling caps.

AMEN AMEN AMEN DON'T LEAVE HOME WITHOUT THEM

 

It would also be a good idea to add a 0.1µF decoupling capacitor across the power rails near the chip.

Nailed it!

 

Your assumption is correct. Are you suggesting ceramic caps for this application ?

Ceramic caps are better than electrolytic caps if they are NP0, X7R or X5R. (Never, never Y5V). The problem is that they may be quite large in both size and cost.
The best compromise is to use film caps such as polyester. They can get really large in size as well but using a larger value timing resistor somewhat makes up for that.

 

Last year I was asked to help with a problem in a design by a member of our club. He was using an ne555 powered from a 9Volt battery, to drive a a circuit that switched at 1Hz between two sine wave audio tones produce by two Wein bridge oscillators.
A click was present on the audio that was being caused by the ne555 even though it was decoupled correctly. Changing to the cmos version completely cured the problem.
An interesting (although not complete) improvement was also made by isolating the track to the ne555 and supplying from the same battery via a resistor and placing a 7.2 volt zener diode across the supply pins of the ne555 as well as 0.1 and 2.2 microfarad capacitors, and connecting the negative battery lead to the 555 ground pin.
There are thousands of 555's available, and different brands do exhibit varying performance depending on the application. The E.bay ones can really lead you a merry dance and are best avoided if at all possible. Buy genuine ones from reputable suppliers for consistency and predictable results.