Mi experiencia: Yoigo y Debian testing. Uso directamente el teléfono móvil (antes un Sony-Ericsson Z610i, ahora un Nokia N900), conectándolo bien por USB o, cuando puedo, por bluetooth.
Ningún problema, va todo fluido. Aunque creo que Yoigo no permite tethering con un "bono del ocho" o con la conexión auxiliar que tienen todas sus prepago (la de 1,20€ diarios), jamás he encontrado limitaciones. Bien es verdad que los smartphones actuales son prácticamente ordenadores y la distinción es absurda.
Además, sólo lo uso para servicios poco consumidores de ancho de banda. Nada de tútubos, P2P o descarga masiva. Consumo entre 100 y 300 MBytes mensuales.
La limitación más llamativa es que siempre estás tras una NAT: nada de montar servidores. También prohíben VoIP, salvo que pagues un extra.
De cobertura muy bien, me muevo por toda España (soy transportista) y es complicado encontrar una zona sin 3/3.5G.
La principal pega de conectar directamente al teléfono es que yo empleo wvdial y cada modelo suele necesitar un wvdial.conf distinto. Pero vamos, una vez encontrado en internet, acaban las pegas. También se puede prescindir del wvdial y emplear alguna herramienta gráfica (creo que Ubuntu tenía una), pero no he probado ninguna.
8€+IVA