I know how we use to struggle setting up cuke4duke, which was Ruby implementation of Cucumber. Installing JRuby, gems and something or other were bound to go wrong.
Good news is java implementation for cucumber is released. (http://aslakhellesoy.com/post/20006051268/cucumber-jvm-1-0-0). I am yet to try it but after reading the article, I am super excited to use it.
More on this soon