Ciao, comincerei controllando su msconfig che non ci siano programmi "strani" in avvio automatico...
Rimossi eventualmente questi ultimi, prova l'avvio tenendo disattivati, a turno, i programmi che usano Internet appena disponibile.

Il non apparire subito dell'icona di connessione vuol dire che il sistema sta elaborando altro, tipo due istruzioni di connessione che si intralciano a vicenda; diverso sarebbe se avessi l'icona ma con la X rossa o il triangolo giallo. Hai mica usato qualche connessione di altro tipo, wi-fi o simili? Controlla se ci sono connessioni remote diverse da quella che usi di solito, e disattivale.