Did you change your system resolution via the preference pane?
Links has it's own setting as well. If it is set for 1024 x 768, you'll have to change it within the game itself, too.
At the main menu, click options, then chooose graphic settings.
(That's what I remember, I'm not sitting at my machine.)