It is helpful in situations like this to take a look at the source code. 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.