Here's a suggestion I posted over at the newsgroup:
The default algorithms for both lsqlin and quadprog accept sparse matrices. However, they only solve problems with equality constraints OR bounds on the variables, but not both. Therefore, since your problem has both, they switch to a dense matrix algorithm.
A possibility is to try the interior-point convex algorithm in quadprog (released in R2011a). It accepts sparse matrices and all combinations of constraints for quadprog. Here's an example:
