Is this the Error 67: Registration Error?
Try rebooting, then starting the web browser, navigate to any web page, then try the tethering.
I get this error sometimes as well, and this usually clears it up. I learned this trick in my old tethering on Windows Mobile days. I don't know exactly what's going on, because I don't know the ins and outs of Sprint's network authentication, but it *seems* like if you are actively using a legitimate data connection (e.g. web browsing) then starting up another prcoess using the connection (e.g. tethering) skips some level of authentication, meaning it doesn't notice that your account shouldn't be doing that.
It shouldn't always require a reboot, if you just fire up the browser before starting tethering. However, once the error 67 starts, I've never been able to bypass it without a reboot.
I know it's a bit of a wishy-washy answer, but I hope that helps.