This was happening in 1.5.29, and is still present in 1.5.30 snapshot r28141 (forge-gui-desktop-1.5.30-20141102.152810-4.tar.bz2).
I hate to bring it up, since it's cool that we have this card at all, but...
Possibility Storm doesn't consistently work correctly. It generally works fine with permanents, exiling the original spell, finding a new one that goes off, then putting the original spell and revealed cards on bottom.
However, when the initially cast spell is an instant or sorcery, it tends to stay on the stack and still resolve, after the "replacement" spell (which resolves as expected). The original spell card is apparently put on bottom of the library - it definitely isn't in the graveyard or exile afterward.
Worst of all is that my testing hasn't returned 100% consistent results. Sometimes instants and sorceries get removed without resolving, although not usually. And sometimes permanents (usually enchantments) stay on the stack and still resolve after their "replacement".
I'm sure that it's not a case of the "replacement" spell PS churns up being another copy of the original triggering spell. I also haven't had any other effects going that might have interfered with the Storm's effect.
Just something to keep an eye on, unless anybody can see a method behind what's happening here. If I notice anything else that might help trace the issue, I'll post it.