There's an amazingly horrible piece of software that manages network connections on KDE: knetworkmanager. And with my recent upgrade to Kubuntu Gutsy from Feisty, it has been behaving as wildly as only a chimp could.
So I decided to simply not use it. There are a few workarounds, like deleting all entries from /etc/network/interfaces (on any Debian-based system), except the one for the localhost and then restarting knetworkmanager. It worked for me till I suspended and resumed.
So what I do instead is this (make sure you have entries in /etc/network/interfaces for eth0, eth1, etc. from the backup file in case you tried the workaround).
[If eth1 is your wireless interface]
$ sudo iwlist eth1 scan
< shows a listing of all available wireless networks found >
$ sudo iwconfig eth1 essid "name"
[where name is the name of the wireless network you want to connect to]
Another step to get a DHCP IP assigned might be needed.
$ /etc/init.d/networking restart
This should be possible even with restarting the dhcp, but I'm not sure which one yet.