A solution that worked for me, hope it works for you too.
I also assigned 13 character password (using characters 0-9 and a-f only) and this did fix my connectivity a few weeks back. However, today, the windows machine, which connects to my mac's 3G internet connection, which is by way of USB Dongle, stopped working again.
I checked to see if I could browse with my iphone, also connected wirelessly. Same problem.
It then occurred to me that I should check the network settings (System preferences/Internet and wireless/Network) to see what was connected to the internet. I noticed that ethernet(en6) was connected to the internet (which must have been my 3G USB dongle) and airport was on but had a self assigned IP address and could not connect to the internet. So I first tried to renew Airports DHCP but still couldn't connect. So I set DHCP manually using self assigned IP address. The IP address for the ethernet(en6) connection that did work was 22.214.171.124 so I used 126.96.36.199 for Airport. This confirmed that airport was now connected to the internet.
However, same problem, neither iphone, nor win machine could connect to the internet.
I then went back to the internet sharing menu and played around with "share your internet connection from" in my case it was ethernet(en6). I changed it to airport and tried to connect but same problem, no connection. After cycling through the various connections I could share from, I went back to Ethenet(en6)
Oddly enough this fixed the connection problem and now iphone and winmachine can connect to the internet again.