passwd -l locks passwords properly by prepending "!" to the encrypted password. however, passwd -u corrupts the encrypted password field. While it removes the prepended "!" it adds 3 characters of garbage on the end, rendering the password useless.
This appears to be working properly as of passwd-0.63-1 from Red Hat Linux 6.1. Could you upgrade the passwd package and check to see if you continue having this problem?
fixed in the current devel tree