I am using Internet Connection Sharing on an Ubuntu laptop, to several clients. (Among them Mac, Windows and Linux)
The primary laptop (Yggdrasil) runs 12.04, and receives an Internet connection via wireless. I can connect, surf, etc., with no problems. I have the wired connection set to ignore IPv6, and IPv4 is set to "Shared to other computers"
The behavior I see on the other computers is that they will connect, receive a DHCP address from Yggdrasil, and all services work between all computers. However, while I can resolve DNS, I cannot contact in any way any computer on the other side of Yggdrasil's wireless connection. Not local hosts, (modem, file server attached to modem, etc), nor any Internet host. Yggdrasil has no problems accessing any hosts on either side of it's connections.