BCM4313 wireless DHCP timing out 'ip-config-unavailable'

I recently had a fight with a Broadcom wireless driver (BCM4313 [14e4:4727]), which was eventually solved by forcing the OS to use the brcmsmac driver. The symptoms were that the WPA-PSK authentication handshake would succeed but DHCP would always timeout, I believe because the underlying 802.11 frames themselves were getting screwed up. Typical logs looked like this:

NetworkManager[948]:  (eth1): DHCPv4 request timed out.
NetworkManager[948]:  (eth1): canceled DHCP transaction, DHCP client pid 2455
NetworkManager[948]:  Activation (eth1) Stage 4 of 5 (IPv4 Configure Timeout) scheduled...
NetworkManager[948]:  Activation (eth1) Stage 4 of 5 (IPv4 Configure Timeout) started...
NetworkManager[948]:  (eth1): device state change: ip-config -> failed (reason 'ip-config-unavailable') [70 120 5]

The state of support for Broadcom wireless chips is quite complicated. Archlinux has a good summary of the mess.