The solution by nukedathlonman in comment #35 fixed the problem for me, too. Details follow.

Machine: Dell XPS M1330 
OS: Ubuntu 10.04 64-bit
Wireless interface:
       product: BCM4312 802.11a/b/g
       vendor: Broadcom Corporation
       version: 01
       width: 32 bits
       clock: 33MHz
       capabilities: pm msi pciexpress bus_master cap_list ethernet physical wireless
       configuration: broadcast=yes driver=wl0 driverversion=5.60.48.36 latency=0 multicast=yes wireless=IEEE 802.11abg

Sample syslog output:

Jun  6 09:18:06 $machine_name wpa_supplicant[967]: WPS-AP-AVAILABLE
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) starting connection '$ssid'
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): device state change: 3 -> 4 (reason 0)
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) scheduled...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) started...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) scheduled...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) complete.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) starting...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): device state change: 4 -> 5 (reason 0)
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2/wireless): access point '$ssid' has security, but secrets are required.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): device state change: 5 -> 6 (reason 0)
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) complete.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) scheduled...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) started...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): device state change: 6 -> 4 (reason 0)
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) scheduled...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 1 of 5 (Device Prepare) complete.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) starting...
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): device state change: 4 -> 5 (reason 0)
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2/wireless): connection '$ssid' has security, and secrets exist.  No new secrets needed.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Config: added 'ssid' value '$ssid'
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Config: added 'scan_ssid' value '1'
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Config: added 'key_mgmt' value 'WPA-PSK'
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Config: added 'psk' value '<omitted>'
Jun  6 09:18:06 $machine_name NetworkManager: nm_setting_802_1x_get_pkcs11_engine_path: assertion `NM_IS_SETTING_802_1X (setting)' failed
Jun  6 09:18:06 $machine_name NetworkManager: nm_setting_802_1x_get_pkcs11_module_path: assertion `NM_IS_SETTING_802_1X (setting)' failed
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Activation (eth2) Stage 2 of 5 (Device Configure) complete.
Jun  6 09:18:06 $machine_name NetworkManager: <info>  Config: set interface ap_scan to 1
Jun  6 09:18:06 $machine_name NetworkManager: <info>  (eth2): supplicant connection state:  scanning -> disconnected