Yo tuve el mismo problema con un proveedor satelital, supe que era el proveedor cuando puse una máquina con windows, le puse un proxy y navegué perfectamente desde debian con ese proxy en windows, comprobando así que mi debian andaba bien, incluso instalé muchas otras distribuciones y supongo que con nmap se daban cuenta que yo usaba linux y me ponían alguna restricción al puerto 80 y similares.
Realiza esa prueba, la pudes hacer hasta con un portátil, usa freeproxy y descartas, ahí podrás pelear con tu proveedor. A mi hermano le navega lento con linux y rápido con windows, pero con el proxy de intermediario le navega rápido linux. ¿que ta? -- "Al principio, el Hombre creó a Dios; y lo creó a su imagen y semejanza. Y el Hombre dio a Dios multitud de nombres, y el poder de que fuera el Señor de toda la tierra cuando al Hombre le conviniere."