A few days ago I have added --backtrace option to Cucumber, since Cloudbees support has recommended it. Looks like it did not provide more information. I have contacted them again. I will let you know as soon as they reply.
Cloudbees support had another idea[1], I have implemented it, but it did not help. I will let you know as soon as we make any progress.
If anybody has ideas on how to debug this, please do let me know.