Do you know if you've formatted over any of the NTFS space?
If the actual partition dimensions (start/end cylinder) have not changed, then you may be able to boot from a recovery disc or Tom's Root Boot or something, and change the partition type in fdisk. If you're talking about /dev/hda, with the first partition being the NTFS partition you want to retag, then you'd
fdisk /dev/hda
I think it's 't' to set the type for a partition, '1' to select the first partition, then 'L' should list the partition types. Look for NTFS and try that.
In my case, I deleted my partition table but, since I was installing multiple OSes I had a little card with my partition geometries at hand. I was able to go back, delete the bad partition table, and create partitions that matched the old layout.
Please note, though, if you've formatted the old NTFS partition, you're unlikely to recover anything. I don't know about the viability of attacking an NTFS partition overwritten with a Linux filesystem with recovery tools. Maybe you could get something back? I tried some Windows file recovery stuff a while back with poor results, so I don't really recall the (free) tool I tried. Maybe some others have suggestions for NTFS recovery programs?