I honestly can't see Conkeldurr being "much" better with Ice Punch. Really, Payback and Stone Edge still seem like the superior options to me, as his list of counters just increases when it uses Ice Punch.
The way I see it, the choice between Ice Punch and Stone Edge is what threatens your team more? I can see Ice Punch/Stone Edge being a slash in the main options now. Ice Punch mainly for Gliscor and to hit 4x ice weak dragons harder, and Stone Edge for Gyarados. Ice Punch also means that you don't ever have to worry about Stone Edge's 80 accuracy screwing you over at the worst possible time.