Recently I've been annoyed by how slowly (30 seconds or so) my laptop connected to Wi-Fi. Although my laptop runs Fedora 15 with a Broadcom chipset it's possible that what I've found will benefit other configurations.
In terms of communication between NetworkManager and wpa_supplicant the process begins with NetworkManager calling the "Scan" method on wpa_supplicant. wpa_supplicant sends various "PropertiesChanged" signals that may type "Scanning" or "BSSs" as determined by the keys of that signal. Ultimately NetworkManager is waiting for a suitable "BSSs".
Failed calls to the "Scan" method are later retried with after an amount of time that increases linearly. The increase in time is 20 seconds, which can be seen in src/nm-device-wifi.c:
#define SCAN_INTERVAL_STEP 20
#define SCAN_INTERVAL_STEP 5
Perhaps "SCAN_INTERVAL_STEP" should be made configurable, but for now I'd recommend trying different values to address slow connection issues.