Comment 8 for bug 996639

I've had this same problem. For now, I just use a work around. To work around:

1) Create a different type of connection besides VNC, I used SSH.
2) Connect to the SSH session, and go fullscreen. You'll notice it works correctly.
3) Start the VNC connection.
4) From fullscreen in the SSH session, move your mouse to the top of your screen and use the "Switch Tab Pages" button to toggle your VNC connection. This will maintain the correct fullscreen, but bring you to your VNC connection.