Primeiro certifique que o Virtualbox não esteja rodando, em seguida crie o novo HD com o tamanho desejado executando o comando:

$ vboxmanage createhd --filename NOVO_HD.vdi --size TAMANHO_DESEJADO

A opção "--size" considera o megabyte como unidade, para 20GB, por exemplo, basta digitar 20480 (20*1024).

Agora faça a transferência de dados do HD antigo para o novo, executando o comando:

$ vboxmanage clonehd ANTIGO_HD.vdi NOVO_HD.vdi --existing

Agora basta usar um particionador de disco de sua preferência (eu utilizo o Gparted disponível na imagem do live cd do Ubuntu) para redimensionar a partição até o tamanho desejado no novo HD virtual.

Obs.: Esse processo de redimensionamento vale para discos virtuais com partições NTFS, apesar de existir um comando (vboxmanage modifyhd) capaz de efetuar o redimensionamento, o mesmo ainda (29/07/2011) não funciona com partições NTFS.