I had the exact same problem on warty warthog (the previous version of ubuntu) and still can't figure it out. I'm trying to build a kde theme from kdelook.org and get this:
checking for Qt... configure: error: Qt (>= Qt 3.1 (20021021)) (headers and libraries) not found. Please check your installation!
I've installed libqt3-dev, libqt3-headers, libqt3-compat-headers and still can't make it work. What packages do I need to make this work?
libqt3-headers and libqt3-dev are both at version 3:3.3.3-7ubuntu3, which sounds like its greater than 3.1

the error sounds fairly ambiguous, how do I find out if it can't find them, if its a version problem, or even whether its the headers or the libraries that is causing the problems?

When you installed those packages, did you reconfigure? After installing those packages ./configure again and it should work! Same thing happened to me yesterday!!!

yes, I am still running the configure script, it has yet to complete without error. I'm doing nothing but reconfiguring. Is there anyone out there who has successfuly done this on ubuntu/kubuntu?

my install is ubuntu with kubuntu-desktop on top of it