Are you using gnome or kde?
In gnome, I've found that the theme may not appear on the main theme list but if you go into the "details" you can still find the different parts of the theme.
For KDE, I've never had much luck. Red Hat, I've heard, altered it drastically from the original. I'm actually installing KDE using all the tar.bz2s from KDE's website right now to see if it helps.
I get exactly the results you do, though-- I follow the directions to the letter and they just don't work.