I use xvfb-run on Debian and it's a breeze:

    xvfb-run -s '-screen 0 1280x1024x8' ./cucumber

Or are you using more advanced Xvfb features, or perhaps running inside containers?