Sicuro non dipenda dal blocco operatore? Con Android 4.1 è stato introdotto il controllo operatore sul traffico dati che può quindi essere bloccato se il gestore decide di non permetterlo con determinate offerte, a meno di non avere smartphone con modem proprietari modificati come quelli dei Samsung.
Ricordo che si era parlato da qualche parte del programma ervius_tether_natter_v2_1 per risolvere il problema...