Old thread I know but I just ran into this issue on RHEL5 trying to mount NFSv4 shares from ExaGrid deduplication appliances.
Many of the hits online are red herrings talking about iptables but that is only an issue if you are sharing from the RHEL server (i.e. NFS server) not if you are mounting on the RHEL server (i.e. NFS client).
Originally RHEL5 didn't support NFSv4 (in fact some of their documentation still says not to use it). But as the OP notes it mounts correctly after boot - just doesn't mount automatically during boot.
I was seeing error during boot on mine when it got to the NFS mounts even though above it it indicated the network interfaces had started:
Mounting NFS filesystems: mount: mount to NFS server 'atlexag1' failed: System Error: No route to host. [FAILED]
On running "chkconfig --list netfs" I saw it was in fact set to start automatically. On review I noticed this script does in fact include mount for both nfs and nfs4.
My mount options were:
myhost:myshare /mymountdir nfs4 hard,intr,retrans=15 1 4
Adding "_netdev" did NOT help:
myhost:myshare /mymountdir nfs4 hard,intr,retrans=15,_netdev 1 4
Reading indicated _netdev is supported by nfs but not nfs4 on some distros including apparently RHEL5.
One post suggested adding the "hard" option but as seen that was already there. However, I noticed they also had the "bg" option for backgrounding the mount. This makes it request the mount but not wait for it to complete during boot. Instead it retries in the background until it succeeds. The error about "no route to host" made me think it was trying to do the mount too quickly after the interface (which is a 10 GigE in our case and not the primary) has been started so it isn't fully functional.
Accordingly I changed my mount options to include "bg":
mysharehost:myshare /mymountdir nfs4 bg,hard,intr,retrans=15 1 4
After doing that and rebooting (which I tested a few times)it no longer output the "no route to host" error and instead of showing as "[FAILED]" it displayed as "[OK}" during boot. After boot completed it had successfully automatically mounted the nfs4 filesystem.
P.S. On RHEL6 these same NFSv4 shares mount automatically without the "bg" option as we originally had it. This appears to only be an issue on RHEL5 (and presumably distros based on it such as CentOS5).