Last night Scott Dier relayed a fix on IRC.  I haven't seen his post
yet, so I'll post the fix myself.  Many thanks to Scott's coworker who
figured it out.

It boils down to AT&T changing their network layout such that the DHCP
server is a long ways from customers in Minnesota.  It might be as far
as Denver.  ISC DHCP (dhclient) sets the maximum hops to 16, which isn't
far enough in this case.  OpenBSD uses dhclient.  dhcpcd (Linux only)
allows for 64 hops.  I didn't pay enough attention to my tcpdump output
to notice what Windows uses.  

Anyway, here is the patch.  It should apply to the ISC tarball, but this
diff is against the OpenBSD 3.1 source tarball.  

ash# diff -u /usr/src/usr.sbin/dhcp/common/packet.c{.orig,}
--- /usr/src/usr.sbin/dhcp/common/packet.c.orig Thu Jun 20 13:36:36 2002
+++ /usr/src/usr.sbin/dhcp/common/packet.c      Thu Jun 20 07:39:01 2002
@@ -146,7 +146,7 @@
        ip.ip_len = htons(sizeof(ip) + sizeof(udp) + len);
        ip.ip_id = 0;
        ip.ip_off = 0;
-       ip.ip_ttl = 16;
+       ip.ip_ttl = 128;
        ip.ip_p = IPPROTO_UDP;
        ip.ip_sum = 0;
        ip.ip_src.s_addr = from;

--
Nate