Have you considered using Ruby's throw/catch instead of exceptions? I did that for Atomy's condition system[1]. They worked great because you can just use the restart names for the throw/catch tags.

[1]: https://github.com/vito/atomy/blob/master/kernel/condition.a...