If you just deleted the partition, you can add it back BUT you should not use Windoze to do that since it might also assume that you want to create a filesystem on the partition, which will cause problems.
If the above programs does not work for you, it is possible to use a Knoppix Live CD to restore the partition. It is easy to do, but only if you are familiar with it. You would use fdisk (under Knoppix, not Windoze even though the name of the command is the same) to add the partition, set the partition type to the correct type. At that point you should be able to access the data.
Knoppix is free and you can download it, make a DVD or CD (depending on the version), boot it and "su" to root, then type "fdisk /dev/XXX" where XXX is the disk.