O problema é que somente o pacote cryptsetup-bin é instalado por padrão no Ubuntu 13.10 (e no AFAIK em versões mais antigas). Isso significa que você pode criar e manipular partições dm-crypt, mas também precisa de cryptsetup package, que contém scripts de inicialização para montar volumes dm-crypt na inicialização.
sudo apt-get install cryptsetup resolveu esse problema.