Power requirements for graphics cards
http://www.realhardtechx.com/index_archivos/Page362.htm
Technically you would have been fine with just a 550 watt power supply. The only reason I suggested the 650 watt unit is so that you have the freedom to upgrade up to a GTX 1080 Ti or Titan X in the future. This particular PSU comes with a 7 year warranty. I personally have a 850 watt unit because I previously had two 980 Ti's in my build. The table above has conservative wattage figures because it assumes that reader may have a poor quality unit. Your AIO water cooler presumably only uses SATA power, and therefore has negligible consumption. Your i7-7700K and GTX 1080 have stock TDPs of 91 and 180 watts respectively; 180 watts for the reference card. My experience is that stock fan curves only consume 80% of max TDP on GPUs. With these figures in mind, you would be below the 50% efficiency curve on your power supply. But if more wattage makes you more comfortable then by all means proceed. I personally think it's more valuable to purchase a higher quality PSU with a slightly lower wattage, then a mediocre quality model with a moderately higher wattage. With that said upgrading from the EVGA G2 650 to either a G2 750 or P2 650 upgrades your warranty length from seven to 10 years. Either upgrade is currently a $30 increase in price on NewEgg.
The reason that I wanted to know the model of your Corsair power supply is to help determine the likelihood of your model being the culprit. If you have a Corsair CX then I would definitely swap it out for a better one before going through the hassle of RMA'ing the video card.
If I were in your position, I would:
Try the GTX 1080 in another system and see if it experienced the same problem.
If GPU worked fine in another system, then I would replace the power supply.
If trying the GTX 1080 in another system wasn't an option, and my power supply quality or age were questionable, then I would take a leap of faith and purchase a high quality power supply. I know that's a $100 investment, but I never compromise on the quality of power supplies. It's cheap insurance for protecting my build.
That's what I would do.