Slow connection and timing out

Hello,

I have a problem with my internet connection.
It was working fine, it's a 100 Mbps connection, cabled through a router spread to 5 computers.
A few days ago, the internet connection became really slow, but functional in a weird way.
It loads web pages as it always did, even if I visit it for the 1st time, even youtube videos work (but only if I set them to potato graphics). It has problems when loading gifs, flash and even downloading a 1 MB file from my own e-mail, in IE it says timed out, in chrome it says network connection error. Visiting the speed test web page, it showed 0.89 Mbps to a nearby server.
All of these problems persist on all other 4 computers (OS varies).

I have tried re-booting the router, changing the cables ...
There was no software update to any, no hardware changes or anything.

Any suggestions?