Partition Magic - это коммерческий продукт, не из дешевых, с точки зрения частоты применения (его цена примерно 100 долларов во Франции), но о нем очень хорошо отзываются. Однако, я никогда его не использовал и не буду его оценивать. Говорят, что он может что угодно делать с разделами, в том числе, и восстанавливать их. Однако, это утилиты для windows, и я не знаю, есть ли в нем DOS-часть. Если необходимо устанавливать Windows для использования Partition magic, то это не очень интересно.
Старый "Мини-HOWTO: Восстановление разделов" (автор Ralf) был почти полностью основан на применении Partition Magic, поэтому я предполагаю, что это хорошее решение, если у вас есть важные данные на Linux-разделе, а возможности вашего Linux малы. Однако, недавно появились свежие версии Partition Magic, и, я думаю, вам необходимо будет прочитать инструкции.