double click the dialup connection, click properties. there should be a tab for sharing. click share this internet connection. this will change the IP address of the nic that connects to the other computer to 192.168.0.1 and its subnet mask to 255.255.255.0. (if you've screwed around with the IP addresses of your nics, you might get a warning). now you should be able to set your other machine (it shouldn't matter that it's running 2k, I've connected linux and mac boxes to a 2k gateway with no problems) to use dhcp. it should get an address from the gateway (your 2k box connected to the internet) - something like 192.168.0.x.
If dhcp doesn't seem to work with your second computer, you'll have to enter the network settings manually. under TCP/IP settings, set its ip to 192.168.0.x (anything from 2-254), and subnetmask to 255.255.255.0, and DNS server to 192.168.0.1 (your 2k box connected to the internet will resolve the ip address for the other machine). you can leave the default gateway line empty.
edit: are you using a cross-over cable to connect the two machines?