Intermittent Internet Access

When I try to get to any web site I sometimes get the message that the address cannot be resolved. If I power cycle my gateway it works. The service provider checked things and feel that the computers (2 of them) may be the issue. I reformatted one computer hard drive and reloaded all software to get rid of any Spyware/Viruses. Still same issue. Could it be the computer?