O Windows não está ditando seus caminhos - na verdade, isso faz parte do problema.
Quando o seu sistema inicializa, uma vez que a BIOS tenha feito a sua coisa e trabalhado quantos discos rígidos você tem, onde eles estão, e como endereçá-los (et cetera), ele passa para uma pequena parte do dispositivo de inicialização primário chamado de registro mestre de inicialização (MBR). Lá dentro, os sistemas operacionais instalam pequenos registros para informar ao computador o que fazer a seguir para inicializar.
Simplesmente removendo o Windows do seu backend, seu MBR não faz mais sentido para o computador, já que ele está referenciando arquivos que não existem. Se você quiser dual-boot, você deve sempre instalar o Windows primeiro por esse motivo. O bootloader da Microsoft carregará várias versões do Windows muito bem, mas tradicionalmente não é tão feliz com outros sistemas operacionais.
Os bootloaders comuns para sistemas Linux são o GRUB e o LILO. Um provavelmente é instalado automaticamente se você instalou o linux de um DVD ou similar. Apenas é sobrescrito quando o Windows instala seu próprio gerenciador de inicialização no MBR. Diferentemente do carregador do Windows, o GRUB inicializará o Windows também, e o LILO também.
Existem algumas maneiras de corrigir sua instalação do Linux, algumas já mencionadas. Eu pessoalmente usaria uma instalação do liveCD linux para inicializar, montar seus dispositivos, chroot em seu ambiente linux e executar o grub-install para recuperá-lo no MBR e fazer o seu sistema inicializar novamente.