He estado probando Ubuntu 9.04, los drivers para la tarjeta inalambrica broadcom bcm4312 que funcionan con Ubuntu 8.10 tambien funcionan para Ubuntu 9.04, se me presento el mismo problema asi que la solucion es la misma que habia posteado para Ubuntu 8.10, no tuve que reinstalar el network-manager
Para hacer funcionar la tarjeta se debe de instalar el siguiente paquete
sudo apt-get install b43-fwcutter