It really should be, and to be honest, we are probably missing something simple. My experience with computers is that the more annoying the problem, the simpler the solution.
Did your modem and/or router come with setup discs? You shouldn't have to run them after the Wizard, but who knows.
Are you losing internet on both machines?
Internet connection sharing turned off?
I did have a problem with my network once after adding a machine. It happened after adding WEP protection and despite adding the correct key a dozen times, I could not connect. My friend works for the cable company(they provide RoadRunner), and he advised to reset the router to default settings(pushing the pinhole button on the back). It seemed stupid to me, but it worked. After all machines were connected to the network and internet, then I tweaked the router settings to their previous security level.