Typically even a tri-state checkbox is still to be treated as a two-state check box in terms of the user's interaction. The user should not be able to switch it between all three states - only between checked and unchecked.
It is only if the information that is related is not in either state that the box is 'displayed' in the tri-state.
What does it even mean for the user to put it into an indeterminate state - it could mean anything in between checked and unchecked. For this reason, tri-states appear complicated because they combine both state and feedback about the current state.
The indeterminate state means the information has to found elsewhere - usually in a tree-like hierarchy below it.
The advantage is that it is compact, and fits in a tree like structure of nodes where all other nodes might have a checkbox. So it becomes visually not so neat to have a different control which fits in to the scheme, especially since (as above) in terms of the user interaction it needs to behave exactly like a two-state checkbox.
So in the right context, the tri-state does a pretty good job - but I would say generally they are commonly found in more technical situations anyway - installers for example - but does the average user install the sort of application that has these options - probably not. Thus for the average user, it's an uncommon control.
What would definitely be wrong, I think is to have a tri-state, where the user can in fact switch between all three states - to literally choose between three different states of something. That frankly would be too awkward and not to mention a bit weird.
The solution I feel would be to always use a three way radio button (which if iconic & connected, can still be very compact) or a simple dropdown that users will be totally familiar with.