As per discussion http://comments.gmane.org/gmane.comp.java.jbehave.user/1342, JBehave maven plugin never uses provided-scope dependencies. This is a pain for us as we package all libraries in separate modules, so they're always in provided scope. Having all of them explicitly changed to compile scope is way too much work.
According to the conversation in the thread, the plugin uses requiresDependencyResolution which has scope runtime by default, excluding provided scope. According to MojoApiSpecification (http://maven.apache.org/developers/mojo-api-specification.html) it's just a matter of changing it to for example compile+runtime to have dependencies from other scopes as well.