So I just did something incredibly stupid. I'll save you the story (unless you want it). Basically I deleted the partitions on a hard drive by mistake thinking it was another corrupt drive attached to the system. I haven't written any data to the drive and I haven't created any new partitions, so I'm hoping everything is still there and a tool should make easy work of it.
It was an NTFS formatted drive that had the partitions deleted using Gparted. I then created a new partition table after that and attempted to create a new NTFS partition in its place, but that last part failed. I then rebooted the machine (Ubuntu server running XFCE) and noticed my mistake. Promptly shut down and removed the drive.
So what are some good (hopefully free) recovery tools I could try assuming it's not totally hosed based on above description?