This is a problem that I really, really hate. I'm trying to compile KMPlayer and it fails because I don't have Qt libraries installed:

checking for Qt... configure: error: Qt (>= Qt 3.1 (20021021) and < 4.0) (headers and libraries) not found. Please check your installation!

I've had such trouble with this before that I always just give up and go get another application when I see this. I'm trying this one more time. What do I need to install? I go to the trolltech site and there are dozens of packages, none of which seem to be called "library".
I really hate it when I see Qt as a dependency. Is it this difficult for everyone?

I dunno about "everyone" else, but I too quit a project build a while back because of the same issue. No matter I put (the required version of) Qt, and no matter what version, the build just wouldn't find it, or if it did find it, it didn't like the version, or if I got past that, the Qmake/Make would quit anyway with cryptic Qt-related errors.
I also found the Trolltech Qt download site to be less than pleasant, with vague documentation and descriptions about the downloads and their purposes.

Good luck!

PS - My workaround for the foreseeable future is to build against GTK whenever possible (unless something wants to build against my running installation of Qt)

Do you perhaps have qt4 installed? If that is the case, the qt4 versions of qmake, etal. may be in the default path.

Did you try entering "qtdoc" to bring up a browser with the full qt documentation? ( from kdesdk package ).

What does "rpm -qa | grep qt" return?

It should be quite easy (It usually works) :
For CentOS : # 'yum install qt-devel'
and Debian : # 'apt-get install libqt3-mt-dev

Rgds