Network computers not able to connect to internet

I have 4 machines running Windows Vista. Every so often updates or something
will mess up the internet to where the host computer accesses no problem, but
the other computers cannot connect.

Usually I end up having to restore to a previous date, and it goes back to
working, now it won't.

I'm running a verizon wireless card to access the net, and I've done all the
typical troubleshooting. If you run diagnostics it blames the connection
problems on the service provider, reseting IP's, etc via Vista diagnostics
does nothing.

Any idea's? The connection is definitely set up as shared, etc. In the past
I also had random issues with the host computer not being able to access the
internet, but the network computers could no problem. Ring any bells with
anyone?

Thanks