Average Joe, there is no mystery to this and I've commented on it before.
Any time you call a 1-800 (or 1-866 or any toll free number) number they are shown your phone number. This cannot be beaten with call privacy (or *67) features.
It's a function called ANI, or automatic number identification.
http://en.wikipedia.org/wiki/Automatic_number_identification
This is why collection agencies want you to call them back on their toll free numbers, as there really is no easy way of screening the call (there are several work arounds like calling through a long distance provider - ie calling cards which provides a cut-out of sorts, but this is not guaranteed to work).
There is nothing illegal in the practice, but you still may want to complain to your telco provider as they seem to have given you the impression that your private number (unlisted?) provides some level of security.