Before you share your internet connection can you connect to the internet and also connect to your other computer as well?
I had sort of the same setup with my laptop a while back (wired cable to my xbox and wireless internet connection though a router, although I never shared the internet through it). The only thing that game me trouble was trying to have both on the same subnet. What I had to do was have my router give my wireless connection a subnet of 1 and set my wired connection to a subnet of 0. For example, my wireless network used 192.168.1.1 while my wired connection used the ip 192.168.0.1. Aside from that I dont kno since I dislike most any microsoft service, especially potentially unsecure internet connection sharing.