I think you would not need to re-format your windows, it just would be ok if you remove anything that remian from McAfee by using McAfee Removal Tools.
Step 1 - Uninstall your McAfee consumer products using Add/Remove Programs in the Windows Control Panel
Windows 2000/XP
1. Click Start, Settings, Control Panel.
2. Double-click Add or Remove Programs.
3. Select the McAfee SecurityCenter product.
4. Click Remove and follow the steps provided.
Windows Vista
1. Click Start, Search, type Programs and Features, and click Go.
2. Double-click Programs and Features.
3. Select the McAfee SecurityCenter product.
4. Click Uninstall and follow the steps provided.
Step 2 - Download and run MCPR.exe
1. Download the removal tool from:
http://download.mcafee.com/products/licensed/cust_support_patches/MCPR.exe 2. Click Save and save the file to a folder on your computer.
3. Navigate to the folder where the file was saved.
4. Make sure all McAfee windows are closed.
5. Double-click MCPR.exe to run the removal tool.
Note: Windows Vista users must right-click MCPR.exe and select Run as Administrator.
6. Restart your computer after receiving the message CleanUp Successful.
Your McAfee product will not be fully removed until the system is restarted.
and now just go to uninstall avast! from add/remove program, reboot your computer and then install avast! again, all problem should be gone