IT guys always say that, without investigating what the infection is first.
It does sound bad though, and time-wise formatting may be quicker and easier.
Back up any important documents etc, to cd or flash, then scan them to ensure you havent saved the infection too.
Stick the Windows disc in the CD drive and reboot to cd.
You will get the option to format. Dont use the quick option in this case.
If possible, download an anti-virus and firewall installers on another computer, for transferring once you have reinstalled. Install those, visit Windows updates then add to your security.