After reformatting a computer, you should always check for updates.
Your computer probably needs them for many things to work, such as Windows Live Messenger.
Go to
Windows Update if you haven't already and download & install all the updates.
BTW, the correct word is format or reformat [wiki]. Reboot is another word for restart.