What happens if you disable the wireless yourself and then try to reconnect? Does it fail then, as well as when it happens due to other circumstances?
If so, you might be looking at a bug. I had, still have I guess - as I've not fixed it but haven't used it lately, a laptop like that. If I disconnect from the wirelessly tethered phone, I have to reboot to connect to it again. In fact, I sometimes have to delete the existing connection and reboot in order for it to connect again.
Mint came that way, so I haven't dug into it. I don't use the device regularly anyhow.