Install Debian Backports kernel automatically

I've got the following pinnings set:

Package: linux-image-amd64
Pin: release a=wheezy-backports
Pin-Priority: 1001

Package: *
Pin: release a=wheezy-backports
Pin-Priority: 499

I get the following error:

$ sudo apt-get install linux-image-amd64
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 linux-image-amd64 : Depends: linux-image-3.16.0-0.bpo.4-amd64 but it is not going to   be installed
E: Unable to correct problems, you have held broken packages.

The policies seem to be correct:

$ apt-cache policy linux-image-amd64
linux-image-amd64:
  Installed: 3.2+46
  Candidate: 3.16+63~bpo70+1
  Package pin: 3.16+63~bpo70+1
  Version table:
     3.16+63~bpo70+1 1001
        499 http://ftp.nl.debian.org/debian/ wheezy-backports/main amd64 Packages
 *** 3.2+46 1001
        500 http://ftp.nl.debian.org/debian/ wheezy/main amd64 Packages
        100 /var/lib/dpkg/status

$ apt-cache policy linux-image-3.16.0-0.bpo.4-amd64
linux-image-3.16.0-0.bpo.4-amd64:
  Installed: (none)
  Candidate: 3.16.7-ckt4-3~bpo70+1
  Version table:
     3.16.7-ckt4-3~bpo70+1 0
        499 http://ftp.nl.debian.org/debian/ wheezy-backports/main amd64 Packages

So I don't get the error. What am I doing wrong?

I'm trying to use puppet to upgrade all Wheezy machines to the backports kernel (a reboot streak is planned), which is why I want to solve it correctly. I could manually login to all servers to run:

sudo apt-get install -t wheezy-backports linux-image-amd64

Which works, but is not as convenient.

UPDATE

As requested:

/etc/apt/preferences.d$ cat linux-image 
Package: linux-image-*
Pin: release a=wheezy-backports
Pin-Priority: 1001

Package: *
Pin: release a=wheezy-backports
Pin-Priority: 499

/etc/apt/preferences.d$ sudo apt-get update
Hit http://debian.kumina.nl wheezy-kumina Release.gpg
.
.
.
Reading package lists... Done
/etc/apt/preferences.d$ sudo apt-get install linux-image-amd64
Reading package lists... Done
Building dependency tree       
Reading state information... Done
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
 linux-image-amd64 : Depends: linux-image-3.16.0-0.bpo.4-amd64 but it is not going to be installed
E: Unable to correct problems, you have held broken packages.
/etc/apt/preferences.d$ aptitude why-not linux-image-3.16.0-0.bpo.4-amd64
Unable to find a reason to remove linux-image-3.16.0-0.bpo.4-amd64.

Solution 1:

Check what that package depends on and what those dependencies need as well. For example I see this for my machine:

#apt-cache  show linux-image-amd64
Package: linux-image-amd64
<snip>
Depends: linux-image-3.16.0-4-amd64

and

# apt-cache  show linux-image-3.16.0-4-amd64
Package: linux-image-3.16.0-4-amd64
<snip>
Depends: kmod | module-init-tools, linux-base (>= 3~), debconf (>= 0.5) | debconf-2.0, initramfs-tools (>= 0.110~) | linux-initramfs-tool
Pre-Depends: debconf | debconf-2.0

Check if dependencies are taken from backports as well.

Solution 2:

sudo apt-get install -t wheezy-backports linux-image-amd64

it is not convenient I know .. but it is the right way to do things without having troubles in future (IMHO of course)

Solution 3:

Change the top line in your preferences to

Package: linux-image-*

Run

apt-get update

Try to install again. If you still get the error, check

aptitude why-not linux-image-3.16.0-0.bpo.4-amd64