Kostka-Foulkes polynomials are q-analogues of weight multiplicities for irreducible representations of semi-simple finite-dimensional complex Lie algebras. They appear in various contexts in representation theory; in particular they are affine Kazdhan-Lusztig polynomials and therefore have positive coefficients. In type A, that is, for the special linear Lie algebra, a positive combinatorial formula has been known since 1978. However, in general, the problem is still wide open. I will give a historical introduction to the problem of finding a positive combinatorial formula for Kostka-Foulkes polynomials beyond type A. Then I will present some joint results with Leonardo Patimo in this direction - in particular such a formula for type B2/C2.