The Selinux blocks some actions of network manager.
This can not be fixed by restorecon -v './dhclient' suggested by trouble shooter. 
Below is the message from setroubleshoot 

Summary:

SELinux is preventing NetworkManager (NetworkManager_t) "search" to ./dhclient
(dhcpc_state_t).

Detailed Description:

SELinux denied access requested by NetworkManager. It is not expected that this
access is required by NetworkManager and this access may signal an intrusion
attempt. It is also possible that the specific version or configuration of the
application is causing it to require additional access.

Allowing Access:

Sometimes labeling problems can cause SELinux denials. You could try to restore
the default system file context for ./dhclient,

restorecon -v './dhclient'

If this does not work, there is currently no automatic way to allow this access.
Instead, you can generate a local policy module to allow this access - see FAQ
(http://fedora.redhat.com/docs/selinux-faq-fc5/#id2961385) Or you can disable
SELinux protection altogether. Disabling SELinux protection is not recommended.
Please file a bug report (http://bugzilla.redhat.com/bugzilla/enter_bug.cgi)
against this package.

Additional Information:

Source Context                system_u:system_r:NetworkManager_t:s0
Target Context                system_u:object_r:dhcpc_state_t:s0
Target Objects                ./dhclient [ dir ]
Source                        NetworkManager
Source Path                   /usr/sbin/NetworkManager
Port                          <Unknown>
Host                          localhost.leo
Source RPM Packages           NetworkManager-0.7.0-0.12.svn4326.fc10
Target RPM Packages           
Policy RPM                    selinux-policy-3.5.13-18.fc10
Selinux Enabled               True
Policy Type                   targeted
MLS Enabled                   True
Enforcing Mode                Enforcing
Plugin Name                   catchall_file
Host Name                     localhost.leo
Platform                      Linux localhost.leo 2.6.27.5-117.fc10.i686.PAE #1
                              SMP Tue Nov 18 12:08:10 EST 2008 i686 i686
Alert Count                   5
First Seen                    Mon 01 Dec 2008 01:02:35 AM HKT
Last Seen                     Mon 01 Dec 2008 01:12:18 AM HKT
Local ID                      b8d4443b-60a1-438f-9697-babf985416e3
Line Numbers                  

Raw Audit Messages            

node=localhost.leo type=AVC msg=audit(1228065138.622:168): avc:  denied  { search } for  pid=2259 comm="NetworkManager" name="dhclient" dev=sda9 ino=286121 scontext=system_u:system_r:NetworkManager_t:s0 tcontext=system_u:object_r:dhcpc_state_t:s0 tclass=dir

node=localhost.leo type=SYSCALL msg=audit(1228065138.622:168): arch=40000003 syscall=10 success=no exit=-13 a0=9600448 a1=21 a2=c17ff4 a3=9600448 items=0 ppid=1 pid=2259 auid=4294967295 uid=0 gid=0 euid=0 suid=0 fsuid=0 egid=0 sgid=0 fsgid=0 tty=(none) ses=4294967295 comm="NetworkManager" exe="/usr/sbin/NetworkManager" subj=system_u:system_r:NetworkManager_t:s0 key=(null)