I had considered that, but if that were the case I would expect black bars at the top and bottom, not a big thick black border!
Ah, I misunderstood. So you're seeing a black border all the way around? What resolution is the game running at? If it's smaller than your monitor's native resolution (this is possible because most games on Xbox 360 run at 1280x720), you can probably get it to fill the screen by changing your graphics card scaling options. In your graphics card control panel, look for something related to scaling and enable it. My personal favorite setting is "preserve aspect ratio", because older games that run in 4:3 will then scale to fill the vertical space on the screen but have black bars on the sides (as opposed to being stretched horizontally to fill the screen, which distorts the image).
If you've got the game set to run at your native res, then I'm not sure what could be wrong.
I'll probably start playing Fez myself tonight, so I can post back if I'm able to get it to go fullscreen.