Here's where I think Behavior Driven Development shows immediate gains, but I'm not sure that test driven development does.
In behavior driven development you approach your tickets in a different way: you sit down with the business person and work with them to define the behaviors that this chunk of functionality should have. I describe this in an entry on my blog, (the post title: Writing Behaviors).
Sitting down with the business person or whomever will help you and them to better understand what the system needs to do for everyone to be happy with that piece of functionality. What it needs to do to be able to be accepted by the QA process you have in place.
Defining testing criteria, then writing those testing criteria into your automated test suite, should reduce the amount of back and forth you get: someone claiming the functionality is broken, because you missed something (either because you legitimately missed something, or because they never told you about it).
It also may help other's perception of your team: if you sit down and define what needs to be done in the system, you could go from, "idiots who overengineer everything and spend time on things we didn't ask for", to, "smart folk who are coming up with useful features".
TL; DR: Behavior Driven Development may show improvements quickly because it's "customer" focused. Test Driven Development, to me, seems to be about testing internals of the codebase that "nobody" cares about and gives less obvious business benefits. (Behavior Driven Development has the immediate, in your face, change: the engineers are suddenly having a lot more face time with the "customer" or business analyst to try to get this right - which should be seen as a good thing. "Oh, they're having a meeting about Feature X, which means there's progress on that front!")