I have the same problem, with a mac-mini internet sharing connection. All the resto of the devies (macbook pro, iphone) where able to get an IP address of the mac mini. I tried disabling the WEP encryption to no avail.

Before we had a Netgear 314 router that was working fine. I just created the connection with an IP address and the mac-mini info and it works, but it's annoying.