Sometimes I'm just so dumb. The problem was that the netmask for my interface was 255.255.0.0, and the netmask that DHCP sends out to everyone is 255.255.255.0. Since they didn't match, broadcasting wouldn't work. I changed the interface to 255.255.255.0 (I set it to 255.255.0.0 so the box could act as aliased gateway), and now happiness abounds. Fred