I have searched for free constrained LLS solvers for some my own purposes - connecting the ones to scikits.openopt and using the ones for solving ralg/lincher subproblems (in future).
So now new LLSP solver is available:bvls. It requires separate installation, see OO LLSP webpage for more details. Other well-known routines - NNLS and WNNLS - are BVLS ancestors.
Thanks to Alan G Isaac and solver authors (Robert L. Parker & Philip B. Stark) who came to agreement of turning bvls license from free-for-non-commercial to GPL and then, moreover, to BSD.
Also, thanks to Pearu Peterson for help with f2py usage.
I have tried some examples with nVars ~ 400...500 and bvls returns better results (r.ff) than translating the problem to NLP and soling via scipy_lbfgsb or scipy_tnc (you could try /examples/llsp_2.py for more details. As for ralg, results are same, but currently time elapsed is much greater).
The solver is intended to be connected to future scipy version. Unfortunately, the BVLS routine is intended for dense problems only (and it's quite bad for my ralg/lincher purposes).
There are other free routines that could be considered - toms/587 (I don't know is the one intended for dense problems only or for sparse ones as well) and BCLS. Latter has GPL (written in ANSI C) and is capable of handling sparse problems, moreover, implicit A matrix via defining funcs Ax and A^T x. BCLS consists of lots files; it has convenient MATLAB API (2 single standalone func for implicit and explicit matrix A) but calling it from C API is very inconvenient, one function is not enough, so I can't connect it to Python via ctypes, the task is too complicated.
As for toms/587, my OS KUBUNTU yields same bug as this one(with ALGENCAN), so I intend to try using the one with next KUBUNTU version.