A instalação do Windows deve preceder a instalação do Ubuntu no tempo
A ordem na tabela de partição ou posição no disco não faz diferença, exceto que o Windows quer partições primárias, como já explicado pelo Android Dev.
O Ubuntu pode ser instalado em uma partição raiz lógica e em uma partição de troca lógica dentro de uma partição estendida. Essas partições podem ser criadas a qualquer momento (também após a instalação do Windows).
Finalmente: o Windows XP precisa de uma tabela de partição MSDOS, o que significa no máximo 4 partições primárias ou 3 partições primárias e uma partição estendida (com várias partições lógicas dentro). E lembre-se de que o XP não recebe mais atualizações de segurança, portanto, evite conectá-lo à Internet.