kaznonさん、まずは起動成功おめでとうございます。
19日のレス後、旅行に出てしまってフォローできていませんでした。
まだ旅先ですが、ようやくネットにつながることができたので見てみたら～という状態です。

今回の問題は表面的な問題点は意外にシンプルで、
1) virtualboxのドライバ(vboxdrv)が正常にインストールされていなかった =#1で判明
2) その原因はlinux-headers-～が正常にインストールされていなかった(or 壊れていたため) =#7で判明
の２点だと思います。

以降は上記２点を解消していく上で判明した問題
3) まずは2)を解消するために(この時点ではインストールがされていないと思われたので) #9でlinux-headers-～のインストールが指示された
4) #10～#13でパッケージマネージャがおかしな状態にあることが判明
5) #20でパッケージマネージャが動かない原因がUbuntu-tweakにあることが判明→#26までで解消
6) #36で実はlinux-headersはインストール済みだけど壊れた状態にあるのではないかという方向に変更　→#48までで解消

----

で、linux-headersが正常な状態に戻ったため、vboxdrvが正常な状態になったことでvirtualboxが起動できるようになったということですね。
横道が多かったために最終的なところまでの過程が複雑になってしまいましたね。
すべてはつながっているので横道だとは言い切れませんが・・・

こういうところがPCの好きな所でもあります。

※4)のパッケージマネージャがおかしな状態は、完全解消には至っていないかもしれません

gontomoさん、ご説明感謝です。説明するのが苦手なもので悩んでいました。（日本語苦手…失言）

kaznonさん、概ねそんな感じです。カーネルヘッダパッケージが壊れていた、というよりはインストールした順番によっては設定が反映されなかったりすることがありますので、--reinstallを行ってみたということです。
kaznonさんが目をつけた「run-parts: executing /etc/kernel/header_postinst.d/dkms」が実行されていなかったんではないかと。（ここ、曖昧）


それはそうと、パッケージ管理システムのワーニングが目障りではありません？
「ソフトウェア・ソース」を起動させて、「ダウンロード元」を一旦別のところにしてから戻すと正常になったりするはずです。
パッケージ管理システムの方はおそらくそれで問題ないでしょう。

問題なのはバージョン違いの「Ubuntu Tweak」で "余計なこと" をしていないか、といったところ。
心当たりがお有りなら、覚悟しておいた方が良いかも…。