Shadow passwords over NIS are always a bad idea. You lost the security, which shadow gives you. A good way to avoid shadow passwords over NIS is, to put only the local system users in /etc/shadow. Remove the NIS user entries from the shadow database, and put the password back in passwd. So you could use shadow for the root login, and normal passwd for NIS user. This has the advantage, that it will work with every NIS client.
If this is not an option for you, you need the GNU C Library 2.x. This is the only Linux libc, which supports shadow passwords over NIS. Linux libc5 has no support for it. Linux libc5 compiled with NYS enabled has some code for it. But this code is badly broken in some cases and doesn't work with all correct shadow entries.
The next problem is PAM. The GNU C Library support Shadow passwords over NIS, but PAM does not, especially pam_pwdb/libpwdb. This is a big problem for RedHat 5.x users. If you have glibc and PAM, you need to change the /etc/pam.d/* entries. Replace all pam_pwdb rules through pam_auth_unix_* modules. This will work.