John Sextro, agile coach at Asynchrony, was recently published in Software Development Times with an article about how to speed up your Cukes:
You’ve probably already defined the problem and have determined that your tests are too slow. What you haven’t done is define success. You will define success in terms of execution time. For instance, if your Cukes are taking 30 minutes, you might define success as, “Make all Cukes run in 20 minutes or less.” The target is up to you and your team to decide. Just remember, the amount of time it takes to run your tests will be inversely proportional to the number of times you will run them. So the faster they are, the more often you will run them.