can you connect to a network manually using iwconfig (as stated above)?
you can try wicd, instead of network-manager:
http://wicd.sourceforge.net/download.php
there is a sources.list entry for it, for easy install. IMO, i like to have network connect at boot without requiring a login, and detest the need for a keyring
IMO, network-manager is notoriously flaky