eu uso ADSL da BrT aqui no RS também...
apesar de achar o serviço muito caro, nunca tive problemas de atendimento por causa de linux ou de roteador. Eles só me pedem que modem eu uso e tal e fazem os procedimentos (todos os procediemntos que eu fiz nunca foram para mim, mas sim para os clientes, que às vezes da pau na linha ou em usuario - eu tenho ADSL a 3 anos e nunca caiu, pelo menos enquanto eu estava em casa).
Além disso, tem a vantagem de poder instalar o modem que você quiser e configurar ele sozinho, sem depender de aparelhos que não se sabe de onde vem, configurados por sei la eu quem e que nem da pra entrar e ver se eles estão te mandando a banda prometida.
Mas eu não vou mentir: na minha cidade só tem BrT. Se desse eu pegava um da NET ou da GVT, só porque eu acho a BrT muito cara.
Quanto ao tópico: PROCON ou ANATEL na cabeça.