What operating system are you running?
There's a thread here that talks about this problem, along with some other problems.
Gemini Rue Someone on page 2 of this thread said they got fullscreen working (Vista 64-bit OS) by running the game in compatibility mode and disabling visual themes and desktop composition.