After trying to figure this out for two months, I've made some progress. I switched from VirtualBox to VMWare Workstation 9 and it started working perfectly. That is until about 2 hours in. Back to the same problem. I also notice now that in the bottom status bar of WICD it will say the wrong SSID. It will show the SSID of the previous network I've connected to rather than the one I'm trying to connect to now.
For example: "Network1: Putting interface up..." while I'm actually trying to connect to Network2 not Network1.
It always seems to give the "Connection Failed: Bad Password" error when it attempts to "Generate WPA configuration file..." This is also odd because it happens even when trying to connect to a WEP secured network.