Wow! That's your problem (or blessing) there buddy!
You may need more rugged hardware for a full Gigabit connection. A 720 MHz single core processor can't theoritically handle a full 1000 Mbps.
As a rule-of-thumb, for your machine to route traffic, you need 1 MHz of CPU per 1 Mbps of WAN speed. This need for CPU resources just increases with: iptables, traffic shaping, etc.
It was happening even when I had 100 Mbps connection as well.
Are you running any applications on your router aside from the default install?
No, it's fairly minimal install.
I have noticed that when this happens, LEDs for other PCs connected via wire turn off while LED for my PC keeps blinking. Router becomes unaccessible. As soon as I unplug and re-plug my PC right away, all LEDs start functioning again and router becomes accessible once again.
Something is crashing perhaps?