Another (possibly utterly stupid) idea:
Create a new Windows account.
Give it admin permissions. Yes, I know your current logon already has them. Indulge me.
Try to run UOA.
It may sound weird, but I've known this to solve other odd UO problems in the past.
Now, as to the dll side of things in filemon, if memory serves, the zone identifier message means a registry key does not exist, or that the key exists but does not contain data. Which key.... your guess is as good as mine.
So, I'd say it's a case of trying to match regmon's output up with filemon, and taking lots of headache tablets while trying to do that!
Tracert failing on the first step or two isn't usually an issue - those are normally routers or servers at your ISP (or home) which are set to ignore such things. So long as the trace reaches its final destination, it doesn't sound as if that's the problem.
Last desperate suggestion (for now!) - instead of launching UOA from the start menu shortcut, start it via a command prompt - change directory to the UOA folder, and run it from there.
*sighs*
Or wait for KR to download / a friend to post a usable DVD or set of CDs to you! Buy a faster PC while you're at it. KR is not fast. Not fast at all.