Ok, my bad, was reading too fast.
Halcyon seems nice, really focus on JSON, which can be handy when building a REST/JSON API.
The answer will be more a personal choice, within what you prefer.
Sinatra has a way to describe routes and endpoints using its DSL that, in my opinion, is way nicer for a simple REST API that Halcyon.
Halcyon looks a lot more like Rails (in routing, controllers etc)., which might not always ease readibility.
Still, there's no real good answer here. Padrino/Halcyon can both work on Rack, Thin or Mongrel, so performance would normally be almost the same.
The difference will be in the style of code you want to write: simple and really explicit DSL like Sinatra/Padrino, or something more like Rails with Halcyon.