I used the sudo script above, and it seem to help, as both of my Parallels network interfaces went green for the first time in awhile (both have 10.x.x.x addresses?), but bridged networking is still not working (clicking over to shared restarts the network and works fine.)
More specifically with ISC dhclient v3.05-RedHat (from Fedora 7) and bridged networking to my Airport I get :
DHCPREQUEST on eth0 [broadcast]
DCHPNAK from 192.168.1.1
DHCPDISCOVER on eth0 [broadcast]
send_packet: Network is down
[keeps trying, times out]
As noted, clicking over to Shared Networking works, and a get a lease to a 10.x.x.x network quickly. (this complicates some network software I'm troubleshooting a fair bit, adding a second layer of NAT...) I'd be happy to provide more data, or try this in some other guest OS, or even a debugging image if it would help you track it down.