It might help to realise that BDD's focus is the conversations. BDD is really an analysis tool which happens to provide some regression testing as a nice by-product.
I've used scenarios at all kinds of levels in conversation; from identifying different stakeholders to see if a release is likely to be well-received, to working out how a module or class should behave.
There are a couple of hints and tips I can suggest for making this easier.
If you've never done it before, it's going to change.
Anything which is new to the domain, or the business, is likely to change. You might realise you're in this space if you're talking through the scenarios, questioning them, and the business say, "Oh, I'm not sure." That's a good sign to stop trying to do BDD and spike something out to get faster feedback, to help the business work out what it is they want. Once the ideas have stabilized, scenarios can be written in retrospect.
All projects have some aspect to them that's new, or you wouldn't be doing them.
If you've done it before, it's boring.
As well as new, differentiating aspects, projects usually have some commoditised aspects to them which are similar to those already done. For instance, if I was producing a new mobile phone, it would still need to make calls. "Make a phone call" is such a well-known scenario that we wouldn't need to talk through it. Similarly, things like "login" or even "user registration" are boring.
Wherever possible, use libraries for these, and then you won't have to write scenarios around them. Also, do the other bits first - have an already-logged in user and work out what he's logging in for. These areas are unlikely to change, so you may be able to get away with manual testing anyway.
If someone has done it before, talking through scenarios can help.
There's a bit between where we have domain-specific requirements, stuff which is relatively well-understood by someone, and where the real uncertainty is mostly around scope rather than the actual behavior of the system.
Talking through scenarios can help the dev team to discover behavior, to draw on an expert's knowledge, and to ensure that the known, valuable behavior is captured.
This is the bit where BDD works best. My tip is to write the most interesting scenarios at the top of the feature file (or wiki, if you're not automating) and delete any scenarios which are duplicated or easy to infer as a result.
Wherever possible, use the scenarios just as examples of how the application works. For instance, if you want to show how validation works, show a couple of examples of how the application helps the user fill in a form. Check that validation is rigorous using unit testing, which is much easier to maintain and quicker to run.
Further reading
If you're interested in this, here are some things I wrote which might help.
BDD in the large
Cynefin for devs, which goes into these three areas in more detail
My tutorial slides, which are all nice and annotated for you, and cover the whole stack too.