I've been going back and forth in my mind on this argument. For a time I was pretty salty about the Uthuk. I've since made some adjustments to my play and list building and am now on a win streak against them. Overall I'm probably at around a 50% win rate against them with Waiqar. But in an Uthuk heavy local meta where you have a good idea of what you are facing every week it's not that hard to build a counter list. Just like @Jukey noted, in a tournament setting you can list build for countering one army only to get caught by another.
I think there are actually two separate questions here.
Are Uthuk overpowered in casual local matches where you know your opponent?
Are Uthuk overpowered in a tournament setting?
My answer to the first question is "not really"... They have a lot of combat related strengths that translate to overwhelming victories at times. Once you crack them you can beat them consistently but you often are winning close games. It's difficult to achieve a high margin of victory against such a high health/high damage army. But in a casual local game a W is a W, so who cares.
My answer to the second question is "most likely"...
There are a few things I think you can say about Runewars that are not under contention:
The game is combat oriented.
Objectives are not as important as killing your opponent.
Winning games by a large margin is more likely to win you tournaments.
Anyone who disagrees with any of these statements feel free to tell me why I'm wrong.
Uthuk tend to be the most point efficient combat army. They are the most likely to win by a large margin (when they do win). This translates to more tournament success. I don't think the problem is as big as some make it out to be... But it exists...
Side note: This is not meant to downplay the skill of anyone winning with Uthuk. This is a game where a good player will beat a bad player 99% of the time even when the bad player has a clearly better list. I also get the impression that no one in the Runewars community is picking their faction because it gives them the best chance of winning. Everyone appears to be picking the faction they like due to a preferred play style or aesthetic, and that rocks. It does however mean that we all tend to be a bit biased when it comes to these discussions. By all accounts @Church14 is an excellent player who has had success with multiple factions. Even never having played against him he often says things on these forums that both demonstrate deep knowledge of the game and ring true to me (as someone who spends too much of his free time thinking about this game). He also seems to really like Uthuk...
As a hard core Waiqar fanatic, I find myself getting a little sensitive about the Lord OP talk of late... I've made my share of "wait and see" arguments about him recently. So I can understand how Uthuk fans could feel the same way about conversations like these.