Late game reg is pretty balanced; really, he isn't that bad at all. He is really good, I will admit, but it's the range, really. Besides, he's so much crap early game he needs to be tough.
I mean, yeah, a level 20 fully equipped reg with an autoattack/mines build is going to be really powerful... but when are you ever going to see a Reg even hit 15 for shrapnel mines (without those, he can't get kills), let alone 20 and fully geared up?
Now, UB is pretty powerful, I'll admit. But it's not really that at any one stage he is overpowered; fully geared up mine regulus puts up a good fight in the late game, QoT can annoy him with shield early game, and his midgame is actually fairly balanced with Erebus. The thing is, he's just right by #1 at ALL stages of the game.
From the beginning, he gets spit. At level 4, he probably has spit 2 + ooze + inner beast or spit 2 + ooze 2, which kills all demigods from level 1-6 (well, maybe not 6.) At level 7, he's even more awesome. Basically, he just keeps getting REALLY, REALLY good level up abilities, and he can kill demigods so fast he can keep his HP and DPS high.
He also doesn't have any real weakness. Creeps? You buy ooze at level 2, you never have trouble with creeps. Mana? Buy the 100% mana sword (it also gives a good buff to weapons damage). Health? Orb of life, high level gear, just the fact he out damages everything so much. Speed? He has high speed, speed buff abilities, and speed debuff abilities. Towers? Spit and go. Demigods? They die. Fleeing demigods? Spit, high speed, speed debuffs. He's just got NO weakness at all, besides his low health (he even has good armor!), so you really really need to spike damage him to win, and he is the king of spike damage.