Se me ocurre que mires los logs del sistema. Desde spotlight directamente teclea Consola, y ya dentro de la aplicación mira en la columna de la izquierda, debajo de Archivos, mira el system.log y abajo del todo, en el desplegable uucp hay un apartado que pone wifid.log. Desactiva el servicio de compartir internet, vuelve a activarlo, prueba con contraseña, sin contraseña y ve mirando los logs mientras te intentas conectar, a ver si arroja algo de luz.
Edit: Buscando por Internet encuentro que la mayoría de usuarios con un problema igual o similar sólo han podido resolverlo haciendo una reinstalación limpia. En otros posts he explicado mis Expedientes X con las primeras instalaciones limpias de Lion y ML, así que si te ves muy puteado y no le encuentras solución, backup de los datos y lo dejas reinstalando mientras cenas o algo...No es lo más óptimo, pero...
De momento si quieres ve comentando lo que ves en los logs y vamos indagando en el tema.