Yes, that's absolutely enough power. More than enough even. I have a 650W for my 670 and it works great.
You might have a defective PSU or GPU, either is possible.
Make sure your PSU is plugged firmly into your wall outlet and all the cables in your case are in properly. If nothing works I'd suggest doing an RMA on your PSU.