where are they getting DHCP addresses from? I am assuming its probably the router, but it needs to be asked.
second, are you using WEP or anything?
third, did you try doing an ipconfig /release then ipconfig /renew on those computers?
Yes from the router, they should be. No encryption. Yes, renew didn't work because they did not have connection information.
UPDATE: So I updated the firmware as just a troubleshooting step and it works now. I didn't see anything in the release notes for the firmware about it, but oh well.