To begin with, it has the troll qualities: reach always helps with opponents closing; high Strength lets it deal out a lot of damage in melee; its rend attack increases the variance of its damage substantially; and of course it regenerates except when damaged by fire or acid.
The half-dragon template (using a red dragon), then, increases its Strength substantially to 31, which gives it claw attacks that do 1d6+10 damage, plus an extra 2d6+15 if it hits with both of them (enough damage to take Kyle from full health to unconsciousness in one full attack). And the red dragon parent gives it immunity to fire (and my party is not carrying much acid). Plus, it gets wings for much greater mobility. The breath weapon is just an afterthought.
And by a naive interpretation, this is merely CR 7 (5 for the troll, +2 for the half-dragon template). I consider this at least CR 8, and arguably higher.
Its true that its hit points are a little lower than most of the monsters my PCs have been fighting, and its AC may be a little low--but it can press the attack again and again. If I wanted to make it even more of a challenge, I'd add some class levels--a barbarian's rage might be especially helpful for this. (And with a Con of 25, it could rage for a long time.)
This has the potential to hassle my PCs considerably until they figure out how to put it down for good.