Why does my circuit work with ceramic capacitors but not electrolytic?
As you say, electrolytic and ceramic caps have different performance at high frequencies.  Basically, electrolytic caps stop acting like caps at much lower frequencies than ceramics do.

Decoupling is a high frequency issue, so decoupling caps need to work at high frequencies.  Electrolytics don't, but ceramics do.