Recently I ran into the problem of not being able to share my VPN connection via ethernet to my Xbox using Windows 7 Starter which came stock on my netbook. After hours of research and failed attempts, I resorted to obtaining a stripped down version of Windows 7 Ultimate (referred to as a "Tiny version" about 1.1GB) and installing it along side my Windows 7 Starter OS.
As far as I know, Windows 7 Starter does not allow for ICS (Internet Connection Sharing) via wired network. There is the option to create an Ad-hoc (wireless) network, but given that I needed to use my wireless connection for connecting to my router, the Ad-hoc network would not work for my purpose.
So now I boot to Windows 7 Ultimate when I need to share my VPN wireless connection to my Xbox via ethernet cable and boot to Windows 7 Starter for all other purposes.
I spent lots of time looking into this and finally came to the conclusion that I needed to install another OS alongside Windows 7 Starter. I hope this helps anyone who is looking for this type of solution and was unable to find an answer anywhere else. If you have any specific questions about how I went about this please feel free to message me.