ping: sendmsg: No buffer space available
This is a known issue, and seems to affect quite a few people.
First I tried installing the proprietary broadcom driver from the 'broadcom-sta-common' package, but that was worse - it wouldn't even recognise the interface. I tried a whole bunch of later kernels and finally found one that worked: 3.1.8.
The ubuntu mainline kernel repo makes trying new kernels easy. Just download and install these debs:
linux-headers-3.1.8-030108_3.1.8-030108.201201061759_all.deb linux-headers-3.1.8-030108-generic-pae_3.1.8-030108.201201061759_i386.deb linux-image-3.1.8-030108-generic_3.1.8-030108.201201061759_i386.deb
Update: spoke too soon. This is still broken on 3.1.8 it just takes longer to manifest. I'm now also seeing a bunch of these messages:
kernel: [25244.951243] ieee80211 phy0: START: tid 1 is not agg'able
Update 2012-01-30: Now I'm also seeing lots of this:
ieee80211 phy0: brcms_c_prec_enq_head: No where to go, prec == 4I'm going to up net.core.rmem and net.core.wmem as suggested in a comment, but that's really only treating the symptoms.
Update 2012-02-10: I realised that at some point I'd put my AP into 'high bandwidth' mode, presumably 802.11n, which worked really badly. I'm guessing that was because of the crowded 2.4GHz spectrum in my area and/or poor linux driver support. When I put it back to regular 802.11g it has been rock solid ever since.