Are you playing wirelessly or through ethernet? Network connectivity can cause issues like this. Another cause could be missing/corrupted files but that's a long shot.
All I can say, if all else fails, try reinstalling UT2004. I remember having an issue like that before, but don't remember how I fixed it exactly. It was around the time I tried my hand at modding/mutating the game (unsuccessfully).