In 9.04 what usually worked for me was the following sequence (aside from
power-down followed by power-up of my FiOS router before these steps):
sudo /etc/init.d/NetworkManager stop
sudo /etc/init.d/networking stop
sudo /etc/init.d/networking restart
sudo /etc/init.d/NetworkManager restart

If that does not work, then try deleting the file:
/var/lib/dhcp3/dhclient-da93150a-*-eth0.lease
and then retry the above steps.

Note: In Ubuntu 9.10 only the networking steps work and the NetworkManager step
does not in the above sequence because it has been changed to an upstart job
(which I have yet to figure out). However, by using the networking steps
coupled with the sudo ifup eth0 - that appeared to work for me in Ubuntu 9.10
(maybe by deleting the lease file as mentioned above).