Isso é certamente possível, eu o instalei em uma partição livre ao lado de 12.04 sem problemas.
Certifique-se de usar o particionamento manual, pois, por padrão, ele tenta usar todo o disco.
Eu fiz não instalar o grub do Kali no MBR (o instalador pergunta se você deseja isso). Em vez disso, após a instalação, iniciei no Ubuntu e executei update-grub : na próxima reinicialização, havia uma opção de menu no grub para iniciar a instalação do Kali.