It seems that creating a network isn't affiliated with Internet Sharing due to your dilemma still occurring.
My advice is to trash your Airport preferences and restart your computer.
From
here :
Mine is still hanging in there. got this advice from a friend though:
OK. A couple more things to try.
1) I assume you already updated to 10.4.1, right?
2) Delete the internet preferences in both these locations:
~/Library/Preferences and /Library/Preferences and restart.
com.apple.internetconfig.plist
com.apple.internetconfigpriv.plist
com.apple.internetconnect.plist
com.apple.internetpref.plist
com.apple.preference.internet.plist
This will cause you to loose all your internet setting so export or
write down your configuration before you do it and of course you will
need to reconfigure everything after you reboot.
3) Delete your Airport keychain in /Applications/Utilities/Keychain Access
There may be another .plist file specifically for wireless, but I do not know since I'm not at home.