Is the remote server accepting connections from your Nagios server on the NRPE port? Is the /usr/local/nagios/etc/nrpe.cfg file setup correctly? Do you have firewall or SELinux active on the remote server and if so did you allow the NRPE traffic?
Type in a terminal on the remote machine:
netstat -alp | grep nrpe
and post output here.
Also post your nrpe.cfg please.