Not sure if this has been posted yet, but I just ran into this issue myself.
Sprint has forced Internet Sharing to use the Phone as Modem profile for dialing out. There is not an option to change it like there used to be:
I poked around a little bit, and it looks like they added this reg key in HKLM/Comm/InternetSharing/Settings --> ForceCellConnection [String value = "Phone as Modem"]
Just change it to "Sprint PCS" and you'll be good to go. Plus you won't have to worry about selecting Phone as Modem at all in the future. Thanks Sprint! That is actually pretty handy!
Edit: LuLuTheMonk made a cab for the reg entry
here.