I've converted about 15 apps from Sinatra to Roda, and a couple of Rails apps to Roda (working on converting my final Rails app). Personally, I've found that the biggest advantages come when the URL structure mirrors your application structure, and you have redundant code in many routes, as that type of code becomes simpler, faster, and DRYer with Roda.
Yes, you can use a before block with wildcard routes with Sinatra, but Sinatra will still traverse the routing list sequentially and recheck the full route for every entry in the list. Unfortunately, while I love Sinatra, have contributed patches to it, and have used it since 0.1.0, the approach doesn't scale well for sites with a lot of routes.
The code non-locality issue shouldn't be ignored, and is probably the largest issue with Roda, but the issue is probably going to happen with any approach that DRYs up the code to the same degree. It's true if you use a before block in Sinatra, or a before_filter in Rails.
The use of a routing tree really isn't an innovative approach (at least not innovated by me). It's been around in Ruby since Rum was released in 2008 (and maybe earlier elsewhere). However, it's not well known, and I hope that Roda brings it into the mainstream.
One of the best things about Roda that I don't think has been mentioned in the comments yet is the plugin system, which I borrowed from Sequel. This makes it easy to extend Roda beyond its very small core. For example, the multi_route plugin makes it easy to scale Roda to larger sites by splitting up routing subtrees into specific files. There are currently about 15 plugins, and I have ideas for quite a few more that I will implement after finishing up my current Rails->Roda conversion.
I apologize that the code on the website isn't syntax highlighted. If anyone can offer their design skills, I would greatly appreciate it.
If you have any questions about Roda, please ask.