Si, el tema de eliminarla mediante powershell lo encontré hurgando por google, mediante un comando y ejecutando como administrador, podías eliminar la aplicación. El problema es que primero tenias que localizarla mediante una lista casi infinita de mierda que viene preinstalada con windows 8.1, y no tengo muchas ganas de entretenerme a buscar, que ya tengo suficiente faena en mi vida.
La solución más rápida, desvincular la cuenta microsoft (hotmail) que usaba para logear a skype (la misma que me pedía para entrar a windows), logearme con la cuenta antigua (usuario de skype), y solucionado!