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.