Did some google'ing, but didn't find a solution - although other people reported the problem as well. Today, after sleeping and clearing my head, I figured out how to solve this.
The wireless card is an Atheros AR5212, this can be verified by issuing:
lshw -class Network
Atheros is supported in Ubuntu (I guess Linux in general) by the ath_pci module, which is part of Madwifi. The module is restricted, as it is not completely free software.
For some reason the restricted modules wasn't updated by the upgrade. The kernel was updated. Kernel and module versions must match, which they now didn't, and thus the ath_pci module didn't work.
The solution is simple, as root issue:
apt-install linux-restricted-modules-`uname -r`
After that the Network Manager automatically took over and connected me to the network.
Just to be safe I did a reboot, and everything still worked.