Double, even triple check your wiring.
Sometimes large value electrolytic capacitors used as the timing cap (like C4 in your circuit) can have a high ESR value, and won't charge up to your expected value. I've had this happen before with a crappy 1uF cap. Changed brands, and then it worked. If you have a way to measure the voltage across C4, it should be charging up to around 6 volts.
You don't say where you're measuring the frequency. If you're measuring pin 3 of IC1, it's only about 1 Hz, so not sure if your meter will read that. Pin 3 of IC2 will change from the base frequency of about 1500 Hz to the modulated value from IC1, every half second. However, if you're having trouble with C4 not charging up, there will be no frequency to measure, it'll just be on constantly.
Also, if you're using an LED instead of a speaker from IC2, you'll never see it change at those frequencies. It will appear to be on constantly.
You can use http://www.ohmslawcalculator.com/555-astable-calculator to calculate different values for this circuit to better suit your needs.
Finally, (I hope this is allowed here) you can check out my book about the 555 timer to learn more about how it functions and build some example circuits on a breadboard. http://www.tiny.cc/555book