I had this exact thing happen to me 2 months ago, lightning hit very near my house, and either sparks jumped into my LAN or the shear EMP from close proximity of the lightning bolt fried my 5 port hub, fried my router, fried the LAN port on my DSL modem, fried the LAN port on the living room computer, fried the LAN port on my laptop, and fried the motherboard on my dev PC. I too had surge protection and battery backup units on EVERYTHING, yet the lightning didn't enter through the wall outlets or even the phone line, it jumped directly into the LAN to fry all that stuff.
The only thing I havn't recovered is the LAN port on the laptop, which is not repairable, so I just use the wireless on that.
I had to buy new lan cards all around, a new router, a new hub, and use the USB port on the DSL modem to connect to the internet. I ran a HTTP and SOCKS proxy on that machine, then ran the CAT5 from that machine to the new router, and by using the proxies was able to get all the computers back on the internet.
The only way this could have been prevented was by using SHIELDED CAT5 cable, which would have not allowed the lightning into the network.
I'm guessing the uplink port on your router is fried, it may even light up green like it's working (mine did), but it won't. Try a different router, or you can run 2 ethernet cards in the gateway machine and do as I did with the proxies.
Good luck!
(EDIT)
oops I just saw where you said you already had a new router... are you sure you are connecting the modem into the router's uplink port and not a normal port (only difference is the uplink port remaps the wires to act as a crossover cable).
Also, there is a certain power-up order to things, first power on the modem, wait a moment, power on the router, wait a moment, then power up computer(s). In most cases the order doesn't really matter since devices will renew their IPs as soon as the signal comes up, but sometimes it does matter.
_____________________
Windows Vista: Just say no.
