Eu também me deparo com esse problema ao usar o Compartilhamento de Internet no OS X. Parece que o Compartilhamento de Internet está configurado apenas para funcionar em redes improvisadas de mac para mac, especialmente quando não estiver usando o Mac OS X Server.
Você pode ter mais sorte ao comprar um roteador sem fio barato , desativando o NAT e usando-o como uma ponte sem fio.