Если настроить интерфейс через interfacec - то NM больше не сможет этим интерфейсом пользоваться - именно поэтому после перезагрузки сеть не ищется.
Можно забить на NM, сделать все как надо, и в автозагрузку запихнуть скрипт подключения к WiFI.
Делаем в консоли, заменяя mywifi на пароль
sudo su
wpa_passphrase mywifi >/etc/wpa_supplicant/password
echo -e 'ifconfig wlan0\nwpa_supplicant -i wlan0 -c /etc/wpa_supplicant/password&\ndhclient wlan0' >/root/wifi.sh
chmod +x ~/wifi.sh
sed -i 's/^exit/\/root\/wifi.sh\nexit/' /etc/rc.local