Problema resolvido. Roteador WRT54G executando o firmware necessário DD-WRT para ser recarregado. A memória flash deve ter se corrompido com o tempo. Antes da correção, os dispositivos Windows não tinham problemas para se conectar ao DHCP, mas o DHCP estava falhando com dispositivos não Windows. Tornou este problema difícil de diagnosticar.