Server lag does not affect fps.
Chac: Everyone makes mistakes. Number of times I've reinstalled Windows on various computers passes three digits, yet I still sometimes forget to install something.
From all the symptoms, it would be either viruses, or no/bad drivers. Viruses are usually out of the question since he just reformatted, so no/bad drivers would be it.
What graphics card do you have? If you have an ati go to
http://ati.com , and if you have an nvidia card, go to
http://nvidia.com .
Find the latest drivers and install.