did you actually format the computer AND reinstall windows? Or just reinstall windows on top of the old version? I know a lot of people who think "formatting with windows" means just installing windows over the old version again
If you did wipe the drive clean, you shouldn't be having this problem. What kind of video does the computer have? Is it onboard, or an AGP card? What type? Nvidia? ATI?