This probably only applies if NT isn't in the first partition on the disk. If you put NT in the first primary partition on the disk, NT most likely won't lose itself when you (re)install another OS.

This paragraph is somewhat guessy: I'm told that NT labels partitions by the order in which they're found. So if you put a partition in position 1, and a partition in position 3, NT will call them 1 and 2. Linux on the other hand will call them 1 and 3. This leads to NT forgetting how to find itself, if you install something in position 2. However, the guy who just did the linux reinstall here is pretty sure that he didn't change the number of partitions on the disk, and NT still forgot how to find itself during boot - so there may be more to the picture than currently meets the eye.

So anyway, here's what you can do to help NT find itself if it gets confused, IE, if you see something like:

OS Loader V4.01
.
Windows NT could not start because the following file is missing or corrupt:
<winnt root>\system32\ntoskrnl.exe

1. Find the boot.ini file. Believe it or not, it won't necessarily be in the NT partition. If you have W98 in a primary partition and WNT in an extended partition, for example, the boot.ini file will probably be on the W98 partition in the \ directory. Mount this partition under linux.
2. Edit this file with a linux text editor.
3. Change the partition(x) to something else. I recommend starting from 0, and working your way up. Unfortunately the relationship between linux partition numbers and microsoft partition numbers isn't all that clear, so we get to just trial-and-error this; fortunately there aren't that many possibilities to try. Anyway, reboot with 0, and see if you can boot NT. If not, go back to step 2, but this time try partition(1), and so on until you find a partition number that works.

In our case, we had to change partition(3) to partition(4). This is strange, as we reportedly didn't insert any partitions (or even add any), but at least it works.