Sorry for the one month bump but this thread deserves another life.
Regice lost out a lot in DPP from ADV with the physical special split. It now could no longer claim to be the only Regi with no weaknesses on the side of its highest defense, and stronger physical attacks in general pushed it all the way down from OU to NU.
Bisharp kinda fits this description. His buff was mostly mechanics changes. Steel no longer resisted Dark. Knock Off was buffed. Fairy type was introduced and weak to Steel. Defog now removes hazards, but Bisharp also enjoys the Attack boost. Sticky Web is also a thing in Low-Ladder that give Bisharp a free +2 Attack.
^^Meh, that's not the standout example. Bisharp rose from UU to OU. Mandibuzz, on the other hand rose all the way from NU, without getting any new moves or whatnot. Buffed Knock Off. Buffed Defog. Buffed Overcoat. Buffed Whirlwind, even (it now penetrates Protect). Stealth Rock less dominant. Not having to care about sun- and rain-boosted attacks (especially Thunder) any more. Sticky Web immunity. Excellent response to new threats such as Aegislash. I could go on.
(Oh, I may be in the minority here but IMO Mandibuzz was quite an unhealthy presence in Gen V NU - it was just too hard for stall teams to kill. It's just that Jynx and Scolipede were worse and so it didn't get noticed.)