Eu também enfrentei esse problema após uma reinicialização após o upgrade para 12.04 a partir da 11.xx. Eu simplesmente removo a caixa virtual do Ubuntu Software Center e a reinstalo após uma reinicialização. Ele funciona muito bem sem perder o sistema operacional atual que instalamos na caixa virtual.