My Windows 7 boots to wi-fi on-line in ~60 seconds.
My Knoppix 6.4.4 LiveUSB does so in 1m46s.
Looking at syslog, it appears that the last 48 seconds
of any boot-up are spent doing Network Manager negotiations.

NM is doing its job here, but doesn't seem as clever as
Win7 in getting its job done; certainly not as fast.
In my case, wi-fi means a Dell internal Broadcom wireless
with a (non-free) wl driver, a DHCP router connected
to the internet via Verizon FiOS at 15 Mb/s. Simple
WEP security. Applet says NM is version 0.8.1.

I have an external wireless adapter that doesn't use a
non-free driver, and get the same results.

Are there some tweaks that would speed up NM?