First backup your data to your external drive. Anything you do to try to recover your partition table risks losing everything. There are some tools that can try to guess and restore your partition table:
http://www.stud.uni-hannover.de/user/76201/gpart/
Some of the hard drive manufacturers have utilities that also attempt to do so, eg maxtor:
http://maxtor.custhelp.com/cgi-bin/m...eHQ9bWJy&p_li=
None of this stuff is foolproof, so backup first.
Another thing to try. Open a console and run:
# cfdisk /dev/hdx
where 'x' corresponds to the foobared drive. If cfdisk sees the partitions correctly, select the "Write" option from the bottom menu(navigate with the arrow keys). This should force a rewrite of the partition table to the mbr as cfdisk sees it. Also, copy down all the cfdisk data; it might come in handy when using other utilities to try and recover the partition table.
After you get the partition table installed/rewritten you will probably have to reinstall grub. I don't know grub so I can't help you there. Check out man grub-install for help.