Io riesco ad utilizzare il tethering solo tramite cavetto perchè tramite bluetooth (io ho windows 7) non riesco a connettermi per problemi di driver.
Con cavetto va molto bene, anche se ogni tanto in aeroporto a fiumicino ho un calo di connessione e poi riparte.
C'è da tenere conto che spesso il campo che segna l'iphone sul display non è sempre vero (mi capitava di avere campo pieno con tanto di copertura 3G e poi risultare irrangiungibile alle chiamate ed a mia volta non riuscivo a telefonare per mancanza di campo).

Ad ulteriore conferma, per esempio sul netbook della mia ragazza il mio iphone con BT è stato connesso per ore, navigando senza problemi (lei ha winzozz XP home).

Credo ti convenga fare qualche tentativo, per determinare da cosa deriva. Magari su altro pc, ma nello stesso luogo in cui usi il tuo oppure sul tuo spostandoti in altro luogo e così via.
Immagino sia una seccatura, ma purtroppo quando si parla di "macchine" si va un po' a tentativi.