I forgot to mention that I did not have this problem with OpenSuse 13.1. Might be related to the old bug https://bugs.launchpad.net/ubuntu/+source/network-manager/+bug/199140