How about Relicanth? That thing was really NU in ADV because it was just really outclassed by a lot of pokemon. It couldn't use its attack with anything because it was only base 90 and its 100/130 defenses were good, but it couldn't take a special hit very well at all, and add a lot of common weaknesses including a 4x weak to giga drain which could really screw it over.
Now this generation, it got an awesome move in Head Smash to compensate for the OK 90 base attack, plus it got an STAB move to actually use with Rock Head. It also got a real movepool to use its defenses with, using moves like Stealth Rock and Rock Polish to punish switches and prepare for a sweep. Plus it now has dual STAB because of Waterfall/Aqua Tail. With the 1.5x boost for Rocks in Sandstorm, now it can take hits from both sides of the spectrum perfectly fine as long as it isn't a grass attack.
It went from being really NU to being what is probably going to be one of the top-used UUs. Pretty damn good for not getting an evolution in my opinion.