Since you have formatted and reinstalled the Operating system, could you please try to check if the computer is complelety uptodate with windows Updates.
Open Internet explorer -then Click Tools
From the drop down menu select Windows update. Let it run completely and then restart the system once (for sure)
Try to update McAfee and let me know the status.
Note: Please make sure that the computer is nt installed with any other security software/you are not behind any proxy servers.
If you still face any issues , get back with some of the below information so as I could nail this down;
How is your computer connected to internet ? (dsl/wireless/cable)
What is the service pack installed in your computer ?
McAfee Online Community Moderator