As a gamer which got 100% on Dark Souls ('xcept Artorias of the Abyss), I never found the game, ultimately, impossible. It was hard, at first. Then it was a matter of mastery. I think too many gamers give up very fast with this game. Once you get the hang of it, everything else is a "breeze".
I agree with your choice about NG+







