Eso que te sucede puede ser por mil cosas: la compañía de internet, la configuración del router, la calidad del router...
Especialmente la configuración, vigila que tengas NAT disponible y demás.
No se de lo que será, pero si quieres una recomendación personal, yo para online siempre recomiendo una compañía que te proporcione la conexión mediante cable (no ADSL) y como router un linksys, especialmente WRT54GL, y ya puestos con firmware tomato (una maravilla).