Sorry, about getting back a bit late....
Which kde rpms do you have installed??? (Also check for the arts rpms)
You might want to try deleting (renaming is a better idea) the ~/.kde folder and try again.
$ rpm -qa --queryformat="%{n}-%{v}-%{r}.%{arch}.rpm\n" 'arts*' 'kde*' | sort
arts-1.5.1-0.1.fc4.x86_64.rpm
arts-devel-1.5.1-0.1.fc4.x86_64.rpm
kdeaddons-3.5.1-0.1.fc4.x86_64.rpm
kdeadmin-3.5.1-0.1.fc4.x86_64.rpm
kdeartwork-3.5.1-0.1.fc4.x86_64.rpm
kdeartwork-icons-3.5.1-0.1.fc4.x86_64.rpm
kdebase-3.5.1-0.3.fc4.x86_64.rpm
kdebase-devel-3.5.1-0.3.fc4.x86_64.rpm
kdegames-3.5.1-0.1.fc4.x86_64.rpm
kdegraphics-3.5.1-0.2.fc4.x86_64.rpm
kdegraphics-devel-3.5.1-0.2.fc4.x86_64.rpm
kdelibs-3.5.1-0.1.fc4.x86_64.rpm
kdelibs-devel-3.5.1-0.1.fc4.x86_64.rpm
kdemultimedia-3.5.1-0.1.fc4.x86_64.rpm
kdenetwork-3.5.1-0.1.fc4.x86_64.rpm
kdenetwork-devel-3.5.1-0.1.fc4.x86_64.rpm
kdepim-3.5.1-0.1.fc4.x86_64.rpm
kdepim-devel-3.5.1-0.1.fc4.x86_64.rpm
kdeutils-3.5.1-0.1.fc4.x86_64.rpm
kdeutils-devel-3.5.1-0.1.fc4.x86_64.rpm
Yea, I'm using the kde rpms from FC4 (not an easy task).
And you might want to use the updated kde-3.5.1 rpms from the kde-redhat project yourself (i386 only);
http://www.kde.org/download/