Sounds like it's time to get to work.
http://www.faqs.org/docs/Linux-mini/Partition-Rescue.html

Looks like that site is down. Can anyone verify that for me?