What is DHCP Rebinding?
When a DHCP lease expires, the DHCP client attempts a renewal - it contacts the original leasing DHCP server, requests a new lease, and if everything goes well it gets one and goes merrily on it's way.
After a period of time, if it doesn't get a response, or it keeps getting negative responses from the original server, it attempts to rebind.
This is essentially the same process as it uses on power-up when it's first requesting a DHCP lease - it sends out a broadcast asking for DHCP servers, and binds to the server that responds positively.
If you keep getting these messages it can indicate a DHCP server misconfiguration, an overloaded DHCP server, or a short timeout period in your DHCP client for the renewing process.
You can get more detailed information at the TCP/IP guide.
-Adam