Acabei de ter esse mesmo problema após a atualização para 16.04.1 a partir de 14.04 (sob o qual o tethering USB funcionou bem por anos).
Com base no syslog, parece que é causado por um conflito com o ModemManager.
Aug 25 13:12:24 outback NetworkManager[2543]: <info> [1472145144.1334] device (enp0s20u2): Activation: successful, device activated.
[...eliding log entries related to nm-dispatcher services]
Aug 25 13:12:38 outback ModemManager[2503]: <info> Creating modem with plugin 'Generic' and '2' ports
Aug 25 13:12:38 outback ModemManager[2503]: <info> Modem for device at '/sys/devices/pci0000:00/0000:00:14.0/usb3/3-2' successfully created
Aug 25 13:12:41 outback ModemManager[2503]: <warn> couldn't load Manufacturer: 'Serial command timed out'
Aug 25 13:12:44 outback ModemManager[2503]: <warn> couldn't load Model: 'Serial command timed out'
Aug 25 13:12:47 outback ModemManager[2503]: <warn> couldn't load Revision: 'Serial command timed out'
Aug 25 13:12:50 outback ModemManager[2503]: <warn> couldn't load Equipment Identifier: 'Serial command timed out'
Aug 25 13:12:50 outback ModemManager[2503]: <warn> couldn't load Operator name: 'SIM failed to handle CRSM request (sw1 106 sw2 130)'
Aug 25 13:12:54 outback ModemManager[2503]: <warn> couldn't load IMEI: 'Serial command timed out'
Aug 25 13:12:54 outback ModemManager[2503]: <info> Modem: state changed (unknown -> disabled)
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.3879] device (enp0s20u2): state change: activated -> deactivating (reason 'connection-removed') [100 110 38]
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.3881] manager: NetworkManager state is now DISCONNECTING
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.4362] dns-mgr: Writing DNS information to /sbin/resolvconf
Aug 25 13:12:54 outback dnsmasq[4348]: setting upstream servers from DBus
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.4430] manager: (ttyACM0): new Broadband device (/org/freedesktop/NetworkManager/Devices/4)
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.4441] device (ttyACM0): state change: unmanaged -> unavailable (reason 'managed') [10 20 2]
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.4445] device (ttyACM0): modem state 'enabling'
Aug 25 13:12:54 outback NetworkManager[2543]: <info> [1472145174.4457] device (enp0s20u2): state change: deactivating -> disconnected (reason 'connection-removed') [110 30 38]
Desativei o ModemManager por meio do comando:
sudo systemctl disable ModemManager.service
E depois reiniciado. Minhas sessões subsequentes de tethering com USB ficaram estáveis desde então.
Tenho certeza de que há uma maneira de configurar o ModemManager corretamente para o meu telefone (um LG G3), mas não tenho necessidade atual de um modem serial, então esse método funciona para mim.