Hay usuarios navegando pero otros no pueden conectarse

A ver, explico mi problema.
Tengo un ciber pequeño con 8 maquinas y 1 mega de internet. Al principio todo iba bien con la velocidad pero en los últimos días me pasa esto: Hay personas chateando o navegando normal, pero cuando alguien inicia en otra máquina se quiere conectar no puede por varios minutos y claro se desesperan y se van. Ya chequé:
-Que esten conectadas en red
-La velocidad de internet (algo baja, de 220 a 440 k de entrada y como 150 de salida)
-Que no hayn P2P o parecidos, revisé máquina por máquina.
-No hay juegos en línea ni en red.
-Ya vacune con el Kaspersky actualizado por si era un troyano o algo.
Es raro, porque por ejemplo yo tengo radio de internet y se sigue reproduciendo y el messenger y páginas como el chat también. Alguien me dijo que podía ser un cuello de botella del proovedor, pero ¿porque pasa cada vez más seguido y en cualquier hora?
Ojalá alguien me pueda ayudar porque ya estoy perdiendo buenos clientes.
Gracias.