Comment 7 for bug 1068341

The proprietary drivers already depend on linux-headers-generic | linux-headers. The optional dependency here is because you might not have a linux-generic kernel installed; you might have linux-lowlatency, or linux-server, and in that case you need linux-headers-lowlatency or linux-headers-server insntalled; these Provide: linux-headers.

What has likely happened here is that you've installed, say, linux-headers-3.5.0-15-generic but have *not* got linux-headers-generic installed. In this case, linux-headers-3.5.0-15-generic Provides: linux-headers, so the dependency is satisfied, but you're going to try booting with linux-image-3.5.0-17-generic for which you don't have headers, so things will break.

The real problem here is that dpkg does not have the ability to specify the real dependency here, which is “This package depends on linux-headers-$FOO for each linux-image-$FOO installed”.