Do the laptops use wireless to connect to your network? Have you tried reseting your router/gateway? When I say reset, I don't mean unplugging it; I mean using a pen to press the tiny reset button on the back of the router for 5-10 seconds. That should return the router to factory defaults, and possibly reset any error that are present. Of course, after you reset and test the connection, you will have to redo all your settings within the router.

-genius_at_work