As I have made conclusion from my own experience with CVXOPT installation (from source, i.e. tarball), as well as from some user comments, CVXOPT sometimes cannot find lapack and blas, despite they are present.
I noticed that it searches for llapack and lblas, and despite I have libblas.so.3 and liblapack.so.3 (installed in my KUBUNTU 8.04, to /usr/lib, via aptitude) it doesn't work. So I had copied libblas.so.3 and liblapack.so.3 into files libblas.so and liblapack.so (same directory /usr/lib) and now all works ok (mb creating soft links would be enough?).
I hope CVXOPT developers will take it into account, mb this problem happens with some other OSes as well.
P.S. If you intend to use OO<->CVXOPT<->glpk connection don't forget to set BUILD_GLPK=1 in CVXOPT setup.py file. glpk should be already installed.