I am having the exact same problem. I am wondering if it is related to the latest version of Virtual Box? I am running v 4.3.6 r91406. I have tried a half-dozen variants of the sources.list, to no avail. I have run apt-get upgrade and apt-get update before running apt-get install -y linux-headers-$(uname -r).
in my case, it can't locate 'linux-headers-3.7-trunk-amd64'
what other info can I provide to help us figure out why apt can't find the files?
