Recently, the butterfly approximation scheme was proposed for computing Fourier transforms with sparse and smooth sampling in the frequency and spatial domains. We present a rigorous error analysis which shows how the local expansion degree depends on the target accuracy and the nonharmonic bandwidth. Moreover, we show that the original scheme becomes numerically unstable if a large local expansion degree is used. This problem is removed by representing all approximations in a Lagrange-type basis instead of the previously used monomial basis. All theoretical results are illustrated by numerical experiments.