Coupla things you might want to consider here.
If the partition you deleted had an install of some distro of linux installed on it. Then it had a kernel associated with that distro too. When you get rid of a kernel or update your kernel you need to mark the old one's and one's you no longer want to appear in grub's menu for complete removal in synaptic.
Then do the sudo update-grub command. Just deleting the partition won't do it. Otherwise that kernel is still no doubt there and grub would still have record of it. Particularly if that older kernel were set to be your default boot partition. Am not familiar with the grub recovery console or what options it gives you to repair your system. Might try booting with the livecd and see what you can do with that.
Could also reinstall grub. There's many free utilities and tools to do that. But afterwards would still make sure you mark all the old kernels on your system for complete removal and then update grub again.
Here's the tute I used when I recently updated my Mint's kernel. Worked perfectly for me in showing me how to properly get rid of older kernels.http://www.howtogeek.com/howto/17787/cl ... boot-menu/
And here's a recent Mint forum thread about a guy having some issues when upgrading his kernel somehow corrupted grub2. Which the answer was reinstalling grub in his case. There's a tool mentioned that he used to reinstall grub. Though should be a couple terminal commands to do it if you feel like learning how to reinstall grub via terminal.viewtopic.php?f=46&t=70749
Plus there are tons of other tools and util to reinstall/repair etc grub. You can find them either searching the forum for "reinstall grub" and similar or on google.