Oh, sorry. I thought you just wanted to know were to find it.
I havn't got UT04, but the other games I have I just entered the Key like you would any other game. Also enter it into "Registration", but you stated you have done this.
Wish I could be more helpful.