According to http://lists.debian.org/debian-powerpc/2006/01/msg00302.html
using upstream's bcm43xx-20060115.tar.bz solves this problem.
** Changed in: linux-source-2.6.15 (Ubuntu)
Status: Unconfirmed => Confirmed
--
bcm43xx does not associate unless "iwlist scan" is invoked.
https://launchpad.net/bugs/38752