In their seminal 1979 paper <a href="http://gdz.sub.uni-goettingen.de/dms/load/img/?PPN=GDZPPN002095319">here</a>,
Kazhdan and Lusztig studied an arbitrary Coxeter group $(W,S)$ and the corresponding Iwahori-Hecke algebra.   In particular they showed how to pass from a standard basis of this algebra to a more canonical basis, with the change of basis coefficients involving polynomials indexed by pairs of elements of $W$ (in the Bruhat ordering) over $\mathbb{Z}$.   Even though the evidence at the time was quite limited, they conjectured following the statement of their Theorem 1.1 that the coefficients of these polynomials should always be non-negative.  (In very special cases this is true because the coefficients give dimensions of certain cohomology groups.)

Several decades later, Wolfgang Soergel worked out a coherent strategy for proving the non-negativity conjecture, in his paper *Kazhdan-Lusztig-Polynome und unzerlegbare Bimoduln uber Polynomringen.* J. Inst. Math. Jussieu 6 (2007), no. 3, 501–525.    This is posted on the arXiv <a href="http://front.math.ucdavis.edu/0403.5496">here</a>.  Now that his program seems to have been completed, it is natural to renew the question in the header:

> What if any implications would the non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials have?

It has to be emphasized that in Soergel's formulation and the following work, the non-negativity is not itself the main objective.   Instead the combinatorial framework proposed was meant to provide a more self-contained conceptual setting for proof of the original Kazhdan-Lusztig conjecture on Verma module multipliities for a semisimple Lie algebra (soon a theorem) and further theorems in representation theory of a similar flavor.   But Coxeter groups form a vast general class of groups given by generators and relations, so it is surprising to encounter such strong constraints on the polynomials occurring in this generality.   

ADDED: There is some overlap with older questions related to Soergel's approach, posted <a href="http://mathoverflow.net/questions/29409/">here</a> and 
<a href="http://mathoverflow.net/questions/92221/">here</a>.