Como você sugere, criar espaço livre encolhendo a partição seria uma boa maneira de superar isso. (Aviso obrigatório: Faça backup dos dados do Windows, se não tiver).
Você pode particionar / redimensionar no Windows ou no Ubuntu / Linux.
Em um caso, eu tive que usar um utilitário no Windows para criar uma partição ext3 no espaço livre que o Ubuntu veria. Depois disso, consegui inicializar o DVD do Ubuntu e finalmente consegui selecionar a partição ext3 e formatá-la no ext4 para o Ubuntu, sem prejudicar a instalação existente do Windows.