I think the balance problems stems from how most teams tend to build/fight - having a big, beefy frontline that protects their backline. Vel'Koz is very immobile however has INCREDIBLE range to make up for this, with extreme "geometry" to sneak in those hits to the backline. With the proposed changes, he becomes a dominant threat to the backline much moreso than he currently is. Getting a quick Q -> W for true damage is incredibly easy to do on their frontline when they're charging at you/retreating.
I personally really like the way they made him deal true damage, right now it deals 50% of your AP + Bonus Damage (based on level) as true, and his Ultimate at max rank deals 80 damage per tick (+12.5% AP per tick) for a total of 10 ticks while slowing enemies hit by 20% (800 base damage). So (for easy number's sake) say you've got 1000 AP. Currently you hit for 500 + 169 true damage with your passive at level 18, that's not including your Q/W/E damage. If you were to nail all procs on someone and then channel your Ultimate, your Ultimate alone would deal 2050 (800 + 1250) true damage. Combined with your passive, it would hit them for 2719 (500 + 169 + 800 + 1250) damage. This is already devastating to tanks if left unchecked, and would certainly 1-shot an unsuspecting ADC/Mage/anyone without a bunch of Health.
His Ultimate hits like a truck as-is, and I feel if they were to take this route they would crush his numbers to make it worthwhile. They could also change it to make him unable to direct his Kamehameha during channel to make it so sidestepping would actually be effective. Or perhaps make him have a sort of "set-up" time, like planting his tentacles in the ground so he doesn't go flying back from the force generated or something of that nature.
I honestly think his problems (for competitive play) currently stem from the fact that he's very predictable, and aside from wave clearing he's a walking ultimate machine. His Ultimate requires him to channel and stand still as well, which compounds the problem of making it very reliable. He also requires targets to stand in a straight line, which is usually a death sentence already for the enemy team with champions like Lux around (aside from Jhin/Caitlyn ultimates, please keep blocking them for your squishies I love you). Someone like Nautilus pushes R and you can wave goodbye to your Ultimate. His E is difficult to land on competent opponents as it has a very specific animation, and his W rarely hits people more than once (where the second part deals the majority of damage). His Q shows you where it's going to detonate at max range, so it's very easy to counterplay in that regard, and him detonating it early is half-way a mind game for both players. Generally you're able to "bait" it out by sprinting directly at him and forcing him to play safe forcing him to assume you will continue your path towards him. Champions like Irelia absolutely crush Vel'Koz by violating his "safe zone" and forcing him to point-blank spells and hope he has enough raw numbers to kill you first. He's a poke-and-siege style champion that excels at extreme ranged warfare. He's been a fairly decent solo-queue mid laner at times, and has annoyed the crap out of enemy bot lanes as a support. Not many champions can match his ranged safety, however he is easily picked off as a trade for this. He's hyper-immobile, and doesn't have something like other immobile mages (say, Syndra, who can throw you off of her or Orianna who can shield herself) have in their kit to survive.
He's also incredibly annoying in ARAM as it's a shooting galley at that point for him, and his KDA's are usually second only to Janna.
