Telmo,
é uma péssima ideia apagar o Windows quando ainda se vai necessitar dele, é para isso que existe o dual boot.
Provávelmente você apagou a partição de serviço de onde seria possível fazer a recuperação.
Os CDs de recuperação do Windows deveriam funcionar, se não funcionam não é um problema relacionado com Linux, dificilmente vai encontrar ajuda aqui, contacta o fornecedor do seu sistema, os CDs de recuperação existem para estas situações...