This could be related to older kdelibs and qt package if you haven't updated them.
And then, make sure that the needed rights for normal users are set on some of the directories for icons in /usr/share and /usr/kde. All the users of the system need execute and read rights on the folders (in order to be able to navigate inside) and read rights on the files. These commands could help (but check out first if the paths match with your installation):
#>find /usr/kde/3.5/share/icons -type d -exec chmod ugo+xr {} \;
#>find /usr/kde/3.5/share/icons -type f -exec chmod ugo+r {} \;
#>find /usr/share/icons -type d -exec chmod ugo+xr {} \;
#>find /usr/share/icons -type f -exec chmod ugo+r {} \;