I can make it work in a simulator, but not with LED's. as such I would assume It would not work if you replaced the LED's,
It does require the LED component to act like a neon bulb, draw no current until it reaches a certain voltage and then suddenly turn on and drop there voltage, the capacitance then increases the voltage seen by the other element and trips it,
This sounds like the LED vendor may have done something non linear inside the LED to prevent it faintly glowing until enough voltage was present on the input.
Based on your current design, a 5V supply should give about a 55Hz flash rate, however it does require an external stimuli such as the switch in the picture to trip it into action.
A self flashing LED would actually be a good example of a device that could cause this behavior, the switch that controls the LED would only power on once the voltage rises high enough, draw a sudden gulp of current, and increase the voltage across the other element
There may be some very marginal case where the voltage gain of a normal LED may be able to cause this, but not yet been able to simulate this.
To the OP:
http://tinyurl.com/yxpezhc3 a falstad circui link for the simulation I have run
Long link below for later visitor:
http://www.falstad.com/circuit/circuitjs.html?cct=$+1+0.000005+10.20027730826997+50+5+43%0Ag+64+256+64+272+0%0Ag+-144+144+-160+144+0%0AR+256+144+288+144+0+0+40+5+0+0+0.5%0AR+64+48+64+16+0+0+40+5+0+0+0.5%0A162+64+96+128+96+2+default-led+1+0+0+0.01%0A162+-16+208+64+208+2+default-led+1+0+0+0.01%0Ar+64+96+64+48+0+1000%0Ar+64+208+64+256+0+1000%0Ac+128+96+128+208+0+0.000001+0.2285886398764465%0Ac+-16+208+-16+96+0+0.000001+-0.22858863987272304%0Aw+64+96+-16+96+0%0Aw+64+208+128+208+0%0Ar+128+96+192+96+0+4000%0Ar+-80+208+-16+208+0+4000%0Aw+128+208+192+208+0%0Aw+192+96+192+144+0%0Aw+192+144+192+208+0%0Ar+192+144+256+144+0+2000%0Aw+-16+96+-80+96+0%0Aw+-80+96+-80+144+0%0Aw+-80+144+-80+208+0%0Ar+-80+144+-144+144+0+2000%0Ar+368+208+368+256+0+2000%0Aw+368+160+368+208+0%0Aw+368+96+368+160+0%0Aw+448+96+448+144+0%0Ar+512+96+512+48+0+2000%0Aw+512+144+512+208+0%0Aw+512+96+512+144+0%0Ar+368+208+432+208+0+4000%0Ar+448+96+512+96+0+4000%0Ac+432+160+368+160+0+0.000001+-1.0145511033526469%0Ac+448+144+512+144+0+0.000001+0.3143925517936923%0Ar+512+208+512+256+0+1000%0Ar+368+96+368+48+0+1000%0AR+368+48+368+16+0+0+40+5+0+0+0.5%0AR+512+48+512+16+0+0+40+5+0+0+0.5%0Ag+368+256+368+272+0%0Ag+512+256+512+272+0%0Aw+432+160+432+208+0%0As+432+208+432+272+0+1+true%0Ag+432+272+432+288+0%0A187+432+208+512+208+0+1000+1000000+1.2+0.000009999999999999999%0A187+368+96+448+96+0+1000+1000000+1.2+0.000009999999999999999%0Ao+42+64+0+12290+1.2000880957814164+0.0001+0+2+42+3%0Ao+43+64+0+12298+1.2000880957812254+0.0001+1+2+43+3%0A
Key points:
If the circuit is not triggered, the LED's would be sitting at roughly 210mV each,
the circuit is relying on one LED to start conducting at a certain voltage, draw a chunk of current to discharge the other sides capacitor, then for that LED to fall under a certain voltage and stop conducting
When it stops conducting, the now partially discharged capacitor gives enough of a delta across the other LED to turn it on and form an oscillation
So there is something to it, just not sure what in an LED would give such a sharp transition,