It is helpful in situations like this to take a look at the [source code](https://github.com/scipy/scipy/blob/master/scipy/optimize/optimize.py).  This is easy because everything in `scipy` is open source!

As you can see from reading the source code, the warning message is printed when `warnflag==2`.  This gets set elsewhere in the code when the `linesearch` function returns None (it fails).   

So why does linesearch fail?  The goal of an optimization algorithm is to find the minima of some objective function through a successive set of iterations.  The line search, in this case, is trying to find a step size where the approximations in BFGS are still valid.  When the Hessian of your function or its gradient are ill-behaved in some way, the bracketed step size could be computed as zero, even though the gradient is non-zero.  

I guess my suggestion is to either go to the literature (Nocedal and Wright has a good discussion of line search and the BFGS method) or to your function and make sure that it is well-behaved in the region you are searching.