I wouldn't be so sure. I had the exact same problem in GNOME.
While I don't have KDE available to check if it's the same, GNOME at least has themes in two parts-- the Window Decorations (what we usually think of as "the theme"), and the Control Functions (the look of buttons, checkboxes, scrollbars and progress bars, window internal color, etc).
What I found was that my themes were in fact installed, as control functions, and what I had to do was go to the "Theme Details" button to get the expanded choices.
As I said, I don't have KDE available to check if it works the same, and it is certainly possible that the standard ./configure make make install put the themes somewhere where KDE can't find them----- hey, that reminds me.
The other problem might be that you need to extract/copy the new themes to a hidden directory in your /home/username folder so that KDE sees them. So check in your hidden folders to see if there's a .kde/themes directory or something.
Also, also (wik

), are you sure that all of the themes you downloaded and installed are for the same version of KDE as the one that you're using? KDE2 themes may be installable (because the libraries are on your system), but won't show up or be useable under KDE3, afaik.
Anyway, sorry to have gone around the mulberry bush (especially since I use KDE so little), but I hope something in here might be useful to you.