autochk program not found
Fortunately I was able to boot into Ubuntu and mount the partition, so I could verify that my data was safe.
After searching on Google, I found some information on using a DOS tool to modify the partition to type 7 (link).
Not having access to a DOS boot disk, I decided to see if I could do the same think in Linux which turned out to be quite simple.
STANDARD DISCLAIMER
I'M NOT RESPONSIBLE IF YOU DESTROY YOUR DATA
PLEASE BE VERY CAREFUL WHEN USING FDISK!!! DO NOT ATTEMPT THIS UNLESS YOU KNOW WHAT YOU ARE DOING AND THEN THINK TWICE!!
Should you still want to proceed, here's how you can do it.
First, boot into Linux. If you do not have a dual-boot system, simply use one of the many Linux boot CD's. Once up and running in Linux, as root, execute the following commands.
First, execute "fdisk -l" this will list your current drives and partitions. Find the drive which contains the problem partition. In my case this was /dev/sda, it could be "sdb", "hda", "hdb" or something else that follows that pattern.
Second, execute "fdisk /dev/sda". Substitute your disk name for "/dev/sda". This will launch fdisk.
Now fdisk will be running so the following command will be executed in the fdisk shell. First, execute "p" to print the partition table. In my case, the problem partition, "/dev/sda2" was incorrectly listed as a Linux partition.
To fix this problem, use the "t" option and set the partition type to 7 (which is the partition type for NTFS).
Now, execute "p" again, to make sure the type is correctly set to NTFS. If all looks good, execute "w" to write out the changes then quit fdisk.
Everything should be OK now, simply restart and you should be able to boot successfully into Windows.
