Después de algunos lios para montar esto, os dejo el mini-howto:

Conectar el modem usb y conectar internet

En el pc1, descargamos los paquetes (botón derecho, guardar como):
* vodafone-mobile-connect_1.99.17-8_all.deb
* usb-modeswitch_0.9.4-1_i386.deb

Aunque sea de vodafone, vale para otros operadores.

Abrimos una terminal y vamos a la carpeta donde los hemos descargado y escribimos:
sudo dpkg -i usb-modeswitch_0.9.4-1_i386.deb
sudo dpkg -i vodafone-mobile-connect_1.99.17-8_all.deb

Si tenemos algún problema de dependencias en la instalación, escribimos:
sudo apt-get -f install

Ya está, conectamos el modem usb con la SIM metida, nos vamos a
Aplicaciones -> Internet -> Vodafone Mobile Connect y se abrirá el programa.

Si no os funciona asi, o no está el programa en el menú, abrimos la terminal y escribimos:
vodafone-mobile-connect-card-driver-for-linux
Y se abrirá el programa.

Configuramos los parámetros para Simyo:
APN: gprs-service
Nombre de usuario: *99#
Password: 1234

Metemos el PIN de la tarjeta.
Pulsamos conectar y ya tenemos internet por 3G.
Mirad que tengamos cobertura, abajo a la izquierda.

Creamos la red local
Conectamos los 2 ordenadores con un cable de red UTP RJ45 directo (es el típico RJ45 que tendremos en casa).
En ambos pcs hacemos:
Buscamos en el panel, a la izquierda del reloj, el icono de redes (2 ordenadores superpuestos).
Hacemos click con el botón derecho del ratón y seleccionamos Editar conexiones
Seleccionamos cableada -> Auto eth0 -> Editar -> Ajustes de IPv4 -> Método: Manual
Una vez aquí:

En el pc1 (el que tiene conectado el modem usb):
* Dirección: 192.168.1.12
* Máscara de red: 255.255.255.0
* Puerta de enlace: 0.0.0.0
Lo demás lo dejamos como está
Pulsamos aceptar.
Abrimos una terminal y escribimos

cat /etc/resolv.conf
En mi caso dice:
nameserver 195.230.105.134
nameserver 195.230.105.135
Apuntamos el primero (nameserver 195.230.105.134)

En el pc2:
* Dirección: 192.168.1.13
* Máscara de red: 255.255.255.0
* Puerta de enlace: 192.168.1.12 (que es la dirección del pc que tiene el modem usb conectado)
* Servidores DNS: 195.230.105.134 (que es el primer valor que apuntamos antes del pc1)
Lo demás lo dejamos como está
Pulsamos aceptar.

Ahora, si todo ha ido bien, deberiamos tener internet en ambos ordenadores.

Si has seguido todos los pasos y sigue sin funcionar, prueba a descargarte el programa Firestarter desde synaptic.
Selecciona como dispositivo detectado Dispositivo telefónico (ppp0) que es el modem usb.
Selecciona “Activar la compartición de la conexión a Internet”
Selecciona como dispositivo de red de área local Dispositivo Ethernet (eth0) que es la tarjeta de red del pc1.
Selecciona Activar DHCP para la red local.
Detalles del servidor DHCP
Crear una configuración DHCP nueva
Dirección IP más baja: 192.168.1.100
Dirección IP más alta: 192.168.1.254
Nombre del servidor: <dynamic> o lo que queráis
Con esto debería funcionar.