For the General Case of an Ubuntu Partition Accidentally Deleted
If you tried techniques to try to recreate the partition, it's likely you've made it even harder to recover. On the other hand, if you've tried proper techniques for undeleting the partition or trying to recover it, that may be very helpful. Either way, it's important you edit your question to include as many details as possible about what you've done since you deleted the partition.
If you don't have documents or other important files in the Ubuntu system (or you do, but they have at least one good backup somewhere else), then I strongly recommend starting over, installing Ubuntu again. It's faster, easier, and less stressful than attempting data recovery.
If you're going to attempt to recover a lost Ubuntu partition, first, read this Ubuntu community wiki page, it's excellent documentation.
As that says, if you mess up your partition table (including by removing partitions), but you don't write data to the inside of where your partitions used to be, your data are intact. This might be one off those nice scenarios. So try these techniques first.
Depending on what you did after you deleted the partition, this might be very simple. I recommend trying GNU Parted's rescue functionality. But if you've decided to attempt to recover data, you should at least run TestDisk and Gpart, too.
(If you need clarification or are able to give specific information about how the partitions were destroyed or about the other things you've tried, that might make it possible for us to help further.
no such partition grub rescue> Scenario
If you deleted a partition and then saw this, that's because you deleted the partition.
But error this does not necessarily mean you deleted a partition! If you don't specifically remember deleting the partition in Windows, then you should:
Check if the partition is still there. You can run
sudo fdisk -l or
sudo parted -l (I usually run both).
If it is not, continue attempting to rescue it. (Or give up. But it sounds like you feel comfortable attempting data recovery--having already done so--and you're willing to put more time into it, so just as long as you know it might not succeed, go for it.)
If it is still there, try reinstalling GRUB to the master boot record (in this situation, I'd suggest a
chroot-based method like this one, but really any method here or here that you haven't unsuccessfully tried yet, should be attempted.
If that doesn't work, try these methods for totally removing GRUB and then putting it back.
If that doesn't work, try using a Windows install DVD/USB, Windows rescue disk (which you can make yourself), or Windows trial install DVD/USB (usually freely downloadable from Microsoft's website) to reinstall the Windows boot loader. Boot into Windows and see what it says about the partition table (but don't modify anything in what might be the Ubuntu partition or where it used to be). Since you have Windows 8 and probably a UEFI system, try going through this (again?) and make sure all the settings are correct.
If you are not sure if it is there, or you don't understand what you're seeing (for instance, in the output of
sudo fdisk -l or
sudo parted -l), or you want to be extra cautious, ask for help! You can edit your question to add the output of those commands.
(People with similar problems where this question doesn't solve it can post a new question, including the output of those commands and any other information that distinguishes it from this question, as well as what makes it similar.)