It turns out that marking this as "solved" was premature..
It seems that I have to get Opera's key on every upgrade, again - it's not persistent on reboot. Furthermore the linux kernel is being held back and not upgraded.
Also, where is the boxee key and how do I get it??
$ sudo apt-get update
W: GPG error: http://deb.opera.com stable Release: The following signatures couldn't be verified because the public key is not available: NO_PUBKEY A2019EA84E7532C8
W: Duplicate sources.list entry http://apt.boxee.tv/ maverick/main amd64 Packages (/var/lib/apt/lists/apt.boxee.tv_dists_maverick_main_binary-amd64_Packages)
$ sudo apt-get upgrade
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages have been kept back:
linux-generic linux-headers-generic linux-image-generic
The following packages will be upgraded:
2 upgraded, 0 newly installed, 0 to remove and 3 not upgraded.