Depending on from which rom you are coming, it could be better to flash an other custom rom first. You can try RR or cm14 and test whether this is working. And if yes, that follow the steps in op for a new and clean installation. It can also depend on the recovery you are using.
I was using RR 5.8.5 when install this one. But the problem now is that I cant even start the RR rom, I got stuck at loading logo too. I tried with TWRP 2.8.7.0 and 3.2.3.0. Only the stock rom is working now.