Which partition did you format? The first partition has the firmware, and the second has the data.
If you only formatted the data partition, you just need to run gtkpod, and select menu File->Create Ipod's Directories. Reboot the iPod, and you should be back in business.
If you formatted the first partition, you will need to extract the firmware file from the Apple Updater. Once you've done that, you can dd the firmware to the iPod. For example:
dd if=firmware of=/dev/sda1
The detailed instructions for doing this are here