Você pode ter no máximo quatro partições não lógicas (significado não-lógico primário ou estendido). Além disso, a maioria das ferramentas suporta apenas uma partição estendida.
O Linux não se importa se está em partições lógicas ou primárias. Eu acho que sua melhor aposta é redimensionar essa partição estendida para que ela cubra tudo, exceto a partição do Windows e a partição PQSERVICE. O Gparted pode fazer isso sem afetar as partições lógicas que já estão lá.
Se a minha resposta não ajudar, inicialize um live CD do Linux e relate a saída de fdisk -l
(digite este comando em um terminal e, se possível, copie e cole a saída).