I would unplug the AirPort Express at this point and see if you can get the Internet sharing with the PC configured.
My Mac mini is connected to the internet by Ethernet cable to my ISP's gateway. I am sharing the Ethernet connection to two iPod Touches via AirPort from my Mac mini. These are the steps for internet sharing from Ethernet to AirPort. See if you have followed them correctly in configuring your kit.
1. In Sys Prefs/Sharing I highlighted Internet Sharing (do not check the box)
2. Share your connection from: Ethernet (from the dropdown menu)
3. To computers using: AirPort (check the little box)
4. Press the button AirPort Options...
5. Name your Network
6. I use Automatic for the channel
7. I encrypt my network using a 40-bit WEP key
8. For a non-Apple device you must use only a 5 alphanumeric character, 40-bit WEP password or only a 13 alphanumeric character 128-bit WEP password
9. Press OK
10. Check the box for Internet Sharing
11. Answer any dialog boxes that pop up
If everything on the Mac end is correct then the issue may lie with the PC since Windows is much more picky about how it is configured. Here is an article that may assist you in getting the PC correct;
http://www.makeuseof.com/tag/how-to-share-the-internet-connection-between-your-m ac-and-a-pc/
Other things that you could try is to name your network with a short name without spaces, such as your Apple Discussions User Name. Also create WEP passwords of only 5 or 13 alphanumerics. Some also suggest an All Caps password.