Started having this problem in 18.04 before I upgraded.
Wifi will not automatically reconnect when I reboot. It requires me to reselect the network and reenter the password each time. Tried removing the connection and remaking it, no dice. All proper checkboxes in NetworkManager are checked. nmcli shows that it's making a NEW connection each time; all the old connections are listed in a merry line. I think this may have started when I tried to bridge my wifi to my wired ethernet connection to get my Vizio Smart TV (which is my primary monitor) to act right. (Spoiler alert: didn't help, but that's Vizio's fault.) The bridge shows up in nmcli and nm-connection-editor. Even if I delete the bridge, it's there again when I restart. Have unplugged the ethernet cable and gone through all the steps again, still the bridge reappears. If I can't get an easy fix with this, can someone at least give me a hand figuring out the proper command line to use with nmcli to pick a named connection (the top wifi connection in nmcli c) and connect it with nmcli d? If necessary I'll just drop that in my startup, but I'd rather get Ubuntu to work the way it's supposed to.
Update: When I try to get nmcli to connect using an older connection (one from any prior reboot) it tells me
Error: Connection activation failed: No suitable device found for this connection.
I looked at the connection files in /etc/NetworkManager/system-connections/ and the difference between them seems to be the uuid and for some reason the MAC address. Isn't the MAC address hardcoded? Hmm…
Added line to NetworkManager.conf to stop randomizing MAC address on connect. Rebooted. No effect.
Best Answer
Edited the connection in Network Manager to disable the automatic connection. Applied. Went back and turned it back on. Applied. Also, (and I'm pretty sure this was the culprit) there was a value in place for the MAC address field. Removed it, then Applied the settings. Checked the profile in system-connections, and the MAC field was blank there, too. Rebooted, and the wifi popped right up.
I think what happened was that it was trying to look for the specific MAC each time it booted up, but the MAC address kept changing, and the new MAC didn't match any of the old profiles so it decided it needed a new profile. By removing the MAC, it was left to auto-configure, turning the existing profile into a one-size-fits-all.