A router would not be overkill, and would probably be your best solution. I would take back the switch you just bought, and get a Linksys or Netgear, or whatever, router. They are pretty cheap, just be sure you get one with 4 ports built in.
This will allow you to set up the machines to get their IP addresses from the router (as it will be running DHCP) and should make the networking a bit easier. Plus, it will make it much easier to share that cable connection, rather than having to buy another NIC and require one machine to always be one, and have to act like a software router.
Be aware of your cable companies policies. Most only allow one IP address; but some tie it to your MAC address. If that is the case, look for a router that will allow MAC spoofing. That is why I went with the Linksys, since it would pretend to have the same MAC address as the comp that used to be directly connected.
To supply us with more info, from the start menu, go to 'run' and type winipcfg (win98) or ipconfig and let us know what the current IP addresses are. Also go to the network control panels, find out if you have the TCP/IP protocols set up for your NIC's, and what comp name and workgroup each one is.
And of course, checking the cables is always a good idea. Since one comp is hooked to the internet, you can just keep switching out patch cables to make sure they all work. (you could even switch NIC's to be sure they both work, that that is more of a hassle.)
To 'ping' just go to the start>programs>ms-dos prompt. that will bring you to a command line. simply type
where the number is the IP address for your other machine. (found using winipcfg or ipconfig)
if it times out, then it is most likely a problem with the hardware
edit: they all call it MAC cloning (instead of spoofing) and you can check your NIC by pinging 127.0.0.1 I believe; though I am a bit sketchy on what that exactly accomplishes.