You didn't specify your version of Windows, so I'll just suggest / ask a few things that come to mind.
This usually happens due to overheating or a faulty cpu or video card.
Did you overclock your system?
Does lowering the resolution and detail levels affect it at all?
If that's not the issue, there may be another program running that's causing a conflict.
You can also try running UT2004 in safe-mode. Create a shortcut and add -safe as a command line parameter.
As a last resort, reinstalling the game might work.
It was indeed due to bad overclock, as I got a new GTX 970 today and trying to find the maximum overclock. I tuned down the voltage and now it works fine. Anyway to lock the framerate to 60fps?