This is the most frustrating bug I've ever ran into on Ubuntu. This was not a problem with 11.10 or even 12.04 betas. When I boot up the wireless is always blocked, whether by a hardware switch (Fn-F2 on my laptop) or by the option in Ubuntu. Occasionally I fool around with fn-f2 in different scenarios and I can get it working. However, any time afterwards when I reboot the problem comes back.
I've looked into many of the other answers and tried the solutions (rfkill, rmmod, etc) to no avail.