Marctronix, this happens because of a .dll Sprint injects into the Internet Sharing process, as a poor mans way to prevent Sprint users from tethering.

Before, to use the Internet Sharing application, users would start an Internet connection via another means (ie starting Internet Explorer) before starting the Internet Sharing application.

The problem would occur if the phone got reset/restarted or the Internet Sharing app got terminated before the "disconnect" properly processed, which caused this error 67 bug.

The link provided above gives information on how to remove this injection so you can connect using the Internet Sharing application directly, and not have to deal with error 67 because of this issue again.