Finally, several Linux drivers are or at least seem to be, access point sensitive. They seem to prefer, as one small example, WPA2-AES and not TKIP. There are more.
Do I gather that with or without NM present, you can connect with Wicd?
And did you ever try setting the static IP address details in NM and see if you can connect?
What I am aiming for is just one connection manager and let's try the one we know connects.
When you stop NM service, doesn't it respawn?