Sure thing -- sounds like you'd selected a screen resolution not supported by your monitor, sorry for the confusion there. But, you can go into your steam apps folder for Tidalis, which on windows 7/Vista by default would be this:
C:\Program Files (x86)\Steam\steamapps\common\tidalis\
And then look inside the RuntimeData folder. You'll see a file settings.dat, and another settings.bak. Delete or rename both of those, and it will forget all your settings and you'll be good to go. Alternatively, if you want to keep all your other settings except this one, you can open the settings.dat file in any text editor and then pretty near the top you will see lines for WindowWidth and WindowHeight, which refer to the fullscreen resolution, and you can set it to something your monitor definitely supports. If that doesn't work, then removing the settings.dat file definitely will.
When you uninstall and reinstall the game from Steam, it doesn't touch the settings.dat files (or any other files that were added after the initial install from Steam, same as with all Steam games), so that's why the reinstall didn't help for this mis-configuration problem.
Hope that helps!