You can also buy a good electronic contact cleanear with no residue and clean your contacts. A tooth brush does not have long enough hair. Try a paint brush with fairly coarse hair which you can trim to adjust rigidity. If you cannot find any contact cleaner, use isopropyl alcohol.
All this should be done in a static free environment, in other words ground yourself before physically touching your mother board. Touching your sink metal water tap will do the trick if you're doing this at home.
finish clean up with a dry cloth (use cotton, not wool as it generates a lot of static electricity)
If possible, get compressed air (in a can) and air dry your socket. This will also blow away any arctic silver which might be plugging your socket.
With a magnifying glass, inspect your work area to ensure that you did not blow any arctic silver between other components leads, if so, clean the area as mentionned above.
At work, we do this on a daily basis but we are well equipped with ionizer and static mats, bracelets etc... (micro miniature repairs)
If you know somebody who works in a similar place, ask him. If your doing it at home, just take your time and inspect your work carefully.
Once it is all cleaned up, insert your old CPU in and remove it. Inspect its contacts and the CPU socket for any arctic silver.
If you find any, repeat cleaning process.
Once satisfied with your cleaning, booth up your computer with the OLD CPU in. If you have no problems, then install your new CPU and there shouldn't be any problems.
Hope this helps
My gaming machine:
P4 2.8 GHz
2 X 512 MHz PC3200 in dual DDR mode
Intel D865PERL MOBO
integrated 6.1 MAX audio
Logitech duo MX mouse and KB
ATI RADEON 9800 PRO