If you're on Vista/Win7 make sure you're running the game as admin.
for a couple of possible workarounds. That's not specific for Celtic Kings but the problem is common to a few games including Celtic Kings.
If none of that works and your native resolution is higher than 1024x768, try to set your resolution to that before launching the game. It's a bit of a pain 'cause after playing you have to revert it, but sometimes it works.
I had one instance of that upside down problem with this game and to this day i'm convinced it was being caused by an app that came with my LG monitor, forte manager or something like that, because after i got rid of it i never had that issue again. I can't confirm it though as i never installed that app again. This one is a long shot, but i thought it was worth mentioning.