Something simple that may have slipped by you is to turn off the Network Manager, if it's running.
Code:
/etc/init.d/NetworkManager stop;/etc/init.d/ypbind
restart;ypcat passwd|head -n2|sed "s/./x/g"
If it's not, then try running system-config-authenticaion and be sure NIS is on and point it towards the yp server of course. There was a bug with this, but I believe it's been fixed and put out through updates. If your Fedora 10 system is fully up to date and NIS still doesn't work then remove "nis" from /etc/nnswitch.conf
If neither of these work, could you post a bit more detail that may reveal why it's not connecting? Are you getting any errors? And if so, what are they?