According to xUnit Test Patterns:
The Ruby-based RSPec kicked off the reframing of TDD to EDD (example-driven development), and the Java-based JBehave followed shortly afterword.
– xUnit Test Patterns pg 33
Actually JBehave predated RSpec by a few years. I remember going to a talk by Dan North of Thoughtworks on JBehave in March of 2005. He presented with examples of JBehave and explained how it got people away from thinking about tests. The very next year at SD West 2006 I attended a half day tutorial by Dave Astels on RSpec. It was still pretty early for RSpec at that point about 0.5, but it was already pretty nice because Ruby is just a lot easier than java for writing a behavior driven DSL.
A bit of poking around reveals JBehave actually dates back to 2003 when Dan North started working on it in at Thoughtworks. I think the issues with making nice DSLs in Java probably led to the much larger success of RSpec in the Ruby community and led to the thinking that JBehave came after.