Simple solution, just tell apt you also want to install grub-efi, regardless of the availability of a new version:
$ sudo apt-get install linux-generic-pae grub-efi
Reading package lists... Done
Building dependency tree
Reading state information... Done
grub-efi is already the newest version.
The following extra packages will be installed:
fdutils linux-doc-2.6.35 linux-source-2.6.35 linux-tools
grub-pc grub lilo
The following NEW packages will be installed:
The following packages will be upgraded:
2 upgraded, 1 newly installed, 0 to remove and 3 not upgraded.
Need to get 34.1MB of archives.
After this operation, 107MB of additional disk space will be used.
Do you want to continue [Y/n]?
And voila, grub-pc is a suggested package and no longer forced upon me! Thanks go out to Frank Groeneveld for suggesting the solution!