I try to run the game and I get the message:
"Your CD key appears to be invalid. You will need to reinstall the game and enter your CD key to fix this problem."
I bought it off GOG last year, it worked just fine last year, but now I can't play it. I never entered a CD key or anything, never received one.

You can contact gog support for a cd key for this game. As for why its asking when it hasn't before did you patch or mod it in anyway sinse playing it last?

I did the megabundlewhatever patch to run it with native widescreen, when that didn't work I uninstalled and reinstalled it. Perhaps that is the problem?

Its possible it left registry entrys over from that patch that require a cd key. Whats the mega bundle whatever patch? Does it include a version update in it because gog games generally come out with the latest official patch.

I'm not so sure about the megapack. This is how I carried out my installation (I have only ever had UT2004 from GOG.
1) Install the GOG.com installer for the game.
setup_ut2004.exe
setup_ut2004-1.bin
setup_ut2004-2.bin
2) Install the UT2004 Mega Pack.
ut2004megapack.exe
3) Install the 32-bit v3369 patch (to correct the error in the Mega Pack which sets the version incorrectly to 1).
ut2004-winpatch3369.exe
4) Install the bonus maps.
AS-Confexia.zip
DM-Forbidden.zip
UT2004-ONSBonusMapPack.zip
Additionally you can then, on top of these instructions, install the optional 64-bit patch. After all of this, if you need a CD key then ask GOG and they'll provide you with two registry keys (one 32-bit the other 64-bit) and you simply run them to add them to your registry.
But yes, as I carried out steps 1) to 4), the patching of the Mega Pack didn't stop it working, and certainly after applying the latest patch to correct the error in the Mega Pack it works fine.

Ahh so it is the megapack. The 64bit patch is kind of pointless for uk2k4 though, any system thats running a 64bit operating system will probably be more then enough to handle it so 32bit mode is normally fine.

Thank you, trying this later.

I don't know whether it is the MegaPack or not. I did research before I applied the MegaPack and I found out that installing the MegaPack puts in an older .ini file that has the wrong version number, so just patch it to 3369 again and the version numbering is corrected.
I agree with the 64-bit thing. I did try it, and it turned out that it's just an alternative executable. No game files are changed, you just get a few new ones that you can use, so you can switch between the 32-bit executable and the 64-bit one, and if you don't want the 64-bit one any more just delete the files that were extracted for it.
I had a look at the registry entries GOG sent me for the CD-keys and I couldn't really see what the difference between the 32-bit and 64-bit one was. The key was the same, the reg location was the same. And thinking about it, I can't see why they would need to be different. GOG did say to use the right one for the version installed though.

It's up to you what you choose to install. However, if you don't install the MegaPack then you'll miss out on some additional maps. GOG only packaged the game with the latest patch simply because this is how the game was distributed, with the MegaPack being an optional, but official, free addon. Anyway, the MegaPack does work, as I said, you just have to repatch the game afterwards as there is an erroneous ini file, and this affected the retail version in the same way, so nothing to do with it being a GOG packaged game.
But as an example, if you get a game from GOG and there's a really good user-made mod available for it, you wouldn't install it because it's not part of the official GOG package? And what if it wasn't from GOG, maybe from Steam or some other DD service, or maybe even a retail disc version?

Didn't even patch anything, still got the error...
Re-installing the game...
Still, maybe include the fix instructions in the downloads page of the installers?