I've had this problem on an LG G3 for months (Verizon.)
It does this every time it shuts down (when it dies, when I have to reboot, etc.) WPS button worked a few times, before that stopped working too. Tried to manually enter it, still nothing. Half the time I just say eff it and go to bed, only to wake up in the morning and find it finally connected. I literally just had this issue again after the battery died; and here's what I did. Whether or not it just finally connected or if it finally solved it, I have no idea.
I connected my phone to my laptop (which was coneect5ed to wifi no problems) made sure it was on data transfer and not just charge. I was messing around in the settings to look for something to do like an internet pass through, and I went into "advanced wifi" and clicked on "Wifi direct."
Nothing ever actually popped up, but as I was in that it connected almost instantly. Like I said, don't know if that's what actually fixed it, but it's worth a shot before doing something like a factory reset.