If you just deleted a partition and did not create a new and format it, you can still rebuild the partition table using a program like Norton Diskedit. It requires information about how the partition table looks, but it can be done (I have done it once).
Also, there is a great program for Linux called gpart that will guess the partition table and write it back to the disk in case you trash the old one. You can get a Linux Distro like EasyLinux (runs of a CD) and then install gpart from a floppy. You can also use Linux distros that runs of a floppy. It has saved my ass a couple of times... gpart can be found here:
http://www.stud.uni-hannover.de/user/76201/gpart/