After replacing my 3rd Gen iPod's HDD with a 16GB Transcend CF card I did a software restore in iTunes and restarted the iPod. That's when I faced the same problem many other people did, the iPod showed the progress bar and kept on restarting.
So I started to collect some information on what might cause the problem and came across this website, explaining how to re-partition an ipod's hdd using the pdisk command in OSX: http://www.bsodmike.com/pages/how-to-upgrade-your-ipod/

I don't have a access to a Mac so I couldn't try pdisk to check the partioning of the drive, but it provided enough information to understand that either the apple_partition_map was pointing at the wrong place (not at the firmware partition), the Apple_MDFW firmware partiton is corrupt or the firmware itself didn't get copied over correctly. Fixing this would involve rewriting the partiton map and rewriting the firmware to the firmware partition. While there should be many ways to do this under OSX or even Linux, I was looking for one to do it under Windows, in my case Vista x64. After a lot of trial and error, this is what I came up with.
You'll need your old iPod HDD and an external CF card reader for this. Also you'll need to download and install a partition manager, the iPodLinux installer and iPodWizard for this procedure.

Please read these instructions beginning to end before you start with the procedure!

1) Put the original HDD back into your iPod and connect it to your PC.

2) Start up iTunes and go the iPod's summary screen. Check 'Enable disk use' and uncheck 'Open iTunes when this iPod is connected'. (important!)

3) Unless your iPod is already up to date, do an update to make sure the latest firmware is on there.

4) Close iTunes and download the iPodLinux Installer from the projects website: http://www.ipodlinux.org/Installer_2
    Get the latest SVN build, direct link: http://www.felixbruns.de/iPod/iPodLinux/svnbuilds/ipodlinux-installer-2.31w-r2394.zip

5) Unpack and run the installer. Stick with the default settings and do the backup. You can quit the installer once the backup is done, all we want is the firmware backup from your old working iPod HDD. In my case the installer crashed after finishing the backup, don't worry if this happens, the firmware backup is still fine.

6) Open an explorer window, navigate to your ipod HDD and make sure hidden files are visible. Backup all four folders (Calenders, Contacts, iPod_Control and Notes) to a folder on your PC.

7) Now make sure your CF card is clean and empty. Windows Disk Management can't delete partitions on Removable Media, so you'll need a seperate program to delete existing partitions. I used an external CF card reader and Paragon Partition Manager to delete all existing partitions and create one FAT32 partition. A digital camera should work as well. If your card comes fresh out the box and you didn't try it in your iPod before, you most likeley won't need to do any of this.

8) Now we're done with preparations. Disconnect your iPod, swap the HDD with your clean CF card and connect the iPod to your PC. Start up iTunes and do a Restore. After iTunes is finished with the procedure, it will tell you to wait for your iPod to restart. In my case it didn't, it just said 'Safe to Disconnect' and stayed in Disk Mode. Close iTunes, disconnect the iPod and restart it manually.

9) Your iPod will be stuck in the restart loop now. Shut it down, take out the CF card and put it in your card reader. You should see the FAT32 partition as a HDD in your PC now. Copy the four folders we backed up earlier onto it now.

10) Start up the iPodLinux Installer again. It will recognize your CF card as an iPod now. Go with the defaults again, but this time uncheck the backup option and finish the installer. You now have a custom loader on your iPod, but the firmware is still corrupt. This will be fixed during  the next steps.

11) Put the CF card back into your iPod, start it up and in the custom startup menu select Disk Mode. Make sure iTunes isn't running and connect the iPod to your PC.

12) Download iPodWizard from  www.GetiPodWizard.com (direct link: http://www.getipodwizard.com/download.php?action=download&file_id=1) and run it.

13) In the top right corner it should say 'Found 1 ipod drives:' and show the drive letter next to it. In the top left where it says Edit Mode select Firmware File, click Open Firmware and select the backup you made in step 5. The file should be called ipod_os_backup.fw. Click Write to iPod and let it finish.

14) That's it. Put the CF card back into your iPod and start it up. You're done and your CF card should be working now. Enjoy your modded iPod ;)


Notes:
These instructions were tested with my 3rd Gen iPod, it might be different with other models. In step 9, when stuck in the restart loop, the 3rd Gen can't be started in Disk Mode anymore. That's why an external CF card reader is needed. If this is different with your iPod and you can still connect it to your PC and be recognizedas a HDD, you might not need one.
When disconnecting your iPod or CF card in external reader from your PC, always use Safely Remove Hardware.
When connecting/disconnecting your iPod HDD or CF card from your iPod, make sure you disconnect power (battery and cable) before. I had the battery disconnected throughout the whole procedure and just powered it from the cable.

Disclaimer:

Know that by performing any one of the modifications outlined in this site you WILL void the warranty in your iPod. Even if you think you know what you're doing, there is a high probability that you will render your iPod useless and end up with a fancy paperweight. iPodHackers.net is in no way responsible for damage to your iPod or yourself. By navigating this site you agree to take responsibilty for your own actions and release iPodHackers.net from any possible liability resulting from the performance of any procedures and/or concepts outlined in this site.

Stupid lawyers.

iPodHackers.net is not affiliated with Apple Inc. iPod is a trademark of Apple Inc.