neither Alt+F11 or Alt+Enter switched me to full screen, did try to start the game full screen already, but that still did not solve the issue.
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.