A
search for '80004002' on the Windows Live Solution Center shows the support staff instructing users to do the following:
No Error Code found : Cannot Sign-in to Windows Live Messenger (Windows Live Solution Center)
Do steps 1, 2, 3.2 and 4. Should fix. If no luck, continue with 5, 6, 7, 8.
If still no luck, see
How to perform Clean Installation of Windows Live Messenger.