Hello,
A few things to check.
Have you moved the router to a new location? It should be kept high off the floor because the high frequency signal can interfere with its self if close to a reflective surface (concrete floor or FireWall).
Is the modem hot? Usually when they they fail it is due to an internal circuit that overheats and causes problems. It could also be a solder joint that has cracked and when it gets hot expands and breaks the connection. But a hot modem is a sure sign of old age and failure.
Do you have any new electronic equipment in the house (or in your neighbours house) such as cordless phones, Wireless speakers, wi-fi music service, etc. It could be interference from another wireless device. Although you did mention that you changed channels and it did not help.
Hope this helps...