The main difference in procedure followed by you and me is :
I download theme archieves (kdm themes) and from theme tab use Install New Theme. Thene browse to the downloaded theme and add it. Actually the links to the themes obtained by Get new themes is wrong sometimes. For example Young Fairies theme links to another php page not kdm archieve. You may find archieves in Eyecandy for your KDE-Desktop - KDE-Look.org or Skin Antics - A Skinning Community: Downloads / KDM & GDM Themes .