kdm does have problems with passwords longer than 8 signs (I do have both shadow and MD5 enabled - standard (KDE) workstation installation). When I use a password with more than 8 signs, I get a login failed (logging in from the console works fine). Using the same password but only using the first 8 signs works fine.
You aren't using MD5 passwords, therefore passwords > 8 characters aren't possible. KDM is doing the right thing.
On a second look, passwd isn't setting MD5 passwords even if they're enabled, so passwd was causing this.
This defect is considered MUST-FIX for Florence Gold release
What are the contents of /etc/pam.d/system-auth?
This has fixed itself with an rpm -Fvh * - don't know for sure what was causing it.