I recently ran into a similar problem during Nvidia drivers installation. I am not a Linux expert so I didn't really know where to start looking, but one thing caught my attention. When I run uname -r, I get
3.2.0-30-generic-pae
Then, dpkg -l | grep linux-headers:
ii linux-headers-3.5.0-18 3.5.0-18.29 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-18-generic 3.5.0-18.29 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-19 3.5.0-19.30 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-19-generic 3.5.0-19.30 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-21 3.5.0-21.32 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-21-generic 3.5.0-21.32 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-22 3.5.0-22.34 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-22-generic 3.5.0-22.34 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-23 3.5.0-23.35 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-23-generic 3.5.0-23.35 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-24 3.5.0-24.37 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-24-generic 3.5.0-24.37 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-25 3.5.0-25.39 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-25-generic 3.5.0-25.39 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-26 3.5.0-26.42 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-26-generic 3.5.0-26.42 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-3.5.0-27 3.5.0-27.46 all Header files related to Linux kernel version 3.5.0
ii linux-headers-3.5.0-27-generic 3.5.0-27.46 i386 Linux kernel headers for version 3.5.0 on 32 bit x86 SMP
ii linux-headers-generic 3.5.0.27.43 i386 Generic Linux kernel headers
ii linux-headers-generic-pae 3.5.0.27.43 i386 Transitional package
And finally, dpkg -l | grep linux-image:
rc linux-image-3.2.0-23-generic-pae 3.2.0-23.36 i386 Linux kernel image for version 3.2.0 on 64 bit x86 SMP
ii linux-image-3.2.0-30-generic-pae 3.2.0-30.48 i386 Linux kernel image for version 3.2.0 on 32 bit x86 SMP
rc linux-image-3.2.0-31-generic-pae 3.2.0-31.50 i386 Linux kernel image for version 3.2.0 on 32 bit x86 SMP
rc linux-image-3.5.0-27-generic 3.5.0-27.46 i386 Linux kernel image for version 3.5.0 on 32 bit x86 SMP
Shouldn't the linux-headers and linux-image packages match? That was also the problem when installing the Nvidia drivers: it couldn't find the package linux-headers-3.2.0-30-generic-pae. It seems the updates somehow got messed up. What can I do about it?