This indeed seems plausible under the powerful assumption that the underlying stat is constant.
Actually it applies to any known relative pattern, for example, that the number increases by 1 each time.
where the additive noise is applied to the center of the first bin?
Yes, you can look at it like that.
I can see how this is better, since the underlying value gets immediately smoothed by binning. However, it does give me a weird hacky feeling...
Is this construction something that has been used before?
Well, the output here is a bin, not a number, and the “exponential mechanism” is the generalization of the Laplace mechanism to handle arbitrary output spaces (kunaltalwar.org/papers/expmech.pdf). In this case, I believe that adding Laplace noise to a bin center and then re-binning is a way to select according to the distribution that the exponential mechanism would prescribe.
Aaron