Hi!
Tried the Linux version, did not get to far, since I can't get trough the "Click to start" title screen. (No matter what I click or press, nothing happens.) I have an Intel GPU and I'm trying it on a laptop, with a touchpad, if that helps.
I'm Linux Mint with XFCE, and Alt+F11 switch fullscreen in applications. Try to find your shortcut for that.
It's a Unity bug, happening quite often on Linux games, and the easiest way to fix it is to go windowed, move the window a little (unstick it from your taskbar), and go fullscreen again.
If it's not working, then it may be related to something else, but i'm pretty sure it's this Unity bug again, from what you said.