JBC, try downloading the latest drivers for your video chipset.
Intel:
http://www.intel.com/
ATI:
http://www.ati.com/
Nvidia:
http://www.nvidia.com/
Don't ever go to the OEM's web site, because they never keep up to date.
Also, I'd advise uninstalling your current video driver, installing the latest video driver (even if it's the same version -- this can fix issues), uninstalling the game, reinstalling the game (from scratch; make sure that everything is gone, except maybe your saved games/HOF), and, finally, make sure that you're completely up to date with the latest DirectX 9 and 10 updates.
I'm sure you've tried all of the above already, but if you're willing to humor me and do it all over again (I know, it sucks, and I hate going through that pain, too), maybe we can get the game running in fullscreen again.
My guess is that somewhere along the line, one of your drivers (I suspect the video driver) was overwritten by an older, Windows 7-default driver.