Estaba configurando un nuevo ordenador con Windows 8 y al intentar asociar la cuenta local con la cuenta de Outlook me dio el error 0x800b0101.
Buscando por internet encontré que este es un error genérico, asociado a multitud de casos. La primera vez que me ocurrió fue en el caso mencionado. Más tarde me ocurrió al usar Windows Update.
Encontré varios foros de gente desesperada con el tema e incluso soluciones oficiales que a mi no me sirvieron para nada pero al fin di con un gran post. Y es que en mi caso el error era tan simple como que el horario de Windows no estaba ajustado. Simplemente actualizándolo a mano tras la instalación de Windows 8 funciona todo perfectamente.
Saludos.