На самом деле достаточно было
apt-get install virtualbox
тогда старый virtualbox 22 заменился на 26 и все работало, а судя по выводу консоли 26е модули к виртуалке у вас стояли.
Хотя странно, такой проблемы быть не должно если в синаптике автообнавление включено, он бы сам разрулил.