I was running into what I believe the same problem everyone else has had with Comcast. Here's the key to what I did to get it working:
1. Turn the router off (as in, pull the power cord out).
2. Turn the cable modem off. Note: for anyone that has the Comcast telephone service, this involves removing the battery from the cable modem in addition to pulling the power cord out. The Comcast VOIP cable modems typically have a battery backup so you can still make phone calls if there's a power outage -- it also seems to preserve some kind of DHCP/MAC relationship that foils efforts to plug-in a new router.
3. Turn the router on -- let it boot up fully
4. Turn back on the cable modem (having returned the battery if you took it out)
Once I was able to fully power-off the cable modem, everything came up swimmingly.