My setup is as follows:- Main ADSL modem / router (switch) configured as DHCP server with address range 192.168.0.25-60 The office machines are configured with fixed IP ( not in the same address pool of course ) and hard wired to this router. A wireless access point ( Router ) is connected to provide Internet access for guests in a separate area. This router is NOT configured as a DHCP server. Wireless authentication is turned off. IP address lease times are set to 4 hours. Sometimes guests are able to connect to the wireless access point but they are not given a valid IP. They get 169.x.x.x addresses. Rebooting their machines does not resolve the problem. The only way to resolve is to reboot the main ADSL/router which is often frustrating for other users who are successfully connected with valid IP and DG. The problem seems to occur more frequently to Apple/Mac guests although it also sometimes occurs with Win machines. I personally use Ubuntu on my Laptop and thus far, never have had any problem connecting and getting a valid IP address in the guest area. One further point of note which may give a clue is that certain guests ( always Apple/Mac ) get lease times of 90 days. However, this does not 'stack out' the number of available addresses and of course, rebooting the router clears them until the next time they login.
The 169.x.x.x addresses are so called "link-local" addresses (see: link-local addresses @ wikipedia). They are usually assigned by the OS when the DHCP server won't give out a valid address or there's no DHCP server at all.
Are you sure the amount of dynamic addresse is high enough and the lease time is small enough?
I think the most likely cause of your problem has already been covered in the previous answers.
For some reason your DHCP thinks it has exhausted the pool of available IPs and thus is unable to provide one to a "guest". Then when the guest is unable to get an IP from DHCP its OS goes with a "link-local" IP.
The fact that a reboot of the router ... which also resets the DHCP IP pool ... seems to "fix" the problem is another reason why I suspect a problem with your router's DHCP IP pool management.
An easy way to explore this specualtion is to drastically increase the size of the IP pool available to your DHCP. If after doing this the problem either goes away or takes a much longer time to occur after rebooting the router, then I think this would imply a problem with freeing up the IPs after a DHCP lease expires.
If increasing the size of the DHCP pool results in no change, then it proves I'm an idiot. (Oh, well. I always suspected as much ...)
Have you looked at the log info for the router doing the DHCP? If there are filters for the log I would set them to whatever the highest level of verbosity is and after the problem occurs see if any of the log messages give you further insight. If your router allows emailing the log when it is full and "wraps", then I also suggest you enable that if you haven't already. Just to ensure you have a chance to see log messages which might be posted at the time the problem occurs.