It's not. It's you. Git gud? :)

What is exactly "accuracy stacked" in the early game? 120? I also very much doubt that UDK has 800+ RES so you can't land debuffs. The game heavily favours ACC over RES in terms of availability - having 3 sets of Accuracy or even better, Perception with some accuracy on each - puts you above 200, and that's not even counting the Banner. Both are easily available from doing a bit of Dragon and a bit of Faction Wars. Virtually no one farms Ice Golem until way into late game, so resist builds are not exactly commonplace in that stage. If you do find an UDK with 300+ resist, you probably won't find another.

Just amp up the ACC to a minimum of 200, which is what will carry you through all of the Dungeons and Normal DT, and you will be fine.

Destroy set is a good counter to regen. If UDK is really so hard to beat in early arena, and everybody uses him, put the dedicated damage dealer of your team in a destroy set. Problem solved.

 This... Skadi is 100% correct. A decent destroy set on your damage dealer (preferably a Spirit Affinity champ) the best way to kill every UDK Turtle team in those low-level Arenas. It's not going to be a fast win... but if UDK teams tick you off as much as they did me... put it on auto, find a good YouTube video, and watch the UDK slowly be destroyed. 

There is also a good post by harleQuin on beating UDK teams in low level Arenas that is worth a read.