Como Bernhard sugeriu, a ordem de instalação pode ser significativa nesse tipo de situação. Se o Windows foi instalado após o Fedora, a opção mais simples seria reinstalar o Fedora.
Por quê?
A maneira mais comum de obter um ambiente com várias inicializações, como você descreveu, é aproveitar um dos populares carregadores de inicialização do Linux; Grub ou Lilo. O gerenciador de partida é um pequeno programa que é responsável por carregar um kernel do sistema operacional na memória, passando o controle de execução ao kernel, o qual continuará carregando o sistema operacional.
Como o computador determina o que ou qual carregador de boot deve executar?
Um setor de inicialização no disco chamado de registro mestre de inicialização [MBR]. O MBR é o primeiro setor, 512 bytes, de um disco. No MBR, geralmente há um conjunto de instruções para carregar o gerenciador de inicialização apropriado, chamado bootstrapping. O Fedora provavelmente instalou um gerenciador de inicialização para você, provavelmente o Grub2, e fez as mudanças apropriadas no MBR.
Então o que?
O Windows sobrescreverá o MBR com seu próprio conjunto de instruções, e é por isso que instalar o Windows primeiro é "recomendado" para esse tipo de configuração. Além disso, se você tiver uma configuração de dois discos com o Windows em um disco e o Fedora em um disco separado, será necessário garantir que seu BIOS esteja configurado para inicializar a partir de qualquer MBR de disco que inclua bootstrapping para o carregador de boot do Linux. Em ambos os casos, o carregador de inicialização do Linux deve estar configurado para executar um processo chamado carregamento em cadeia. É quando um software atualmente em execução é substituído por um software diferente. Nesse caso, às vezes, você deseja substituir o carregador de inicialização do Linux pelo Windows para poder inicializar nesse sistema operacional. Presumindo uma instalação do Grub2 mais uma vez, sua configuração pode se parecer com:
menuentry "Microsoft Windows XP" {
insmod chain
set root=(hd1,1)
drivemap -s hd0 hd1
chainloader +1
}