I think you have a legitimate complaint against your cell phone provider. 8xx numbers are really automated collect calls. You should be charged only for air time. If they don't see it that way, tell them you are going to write to the FCC and ask their opinion.
Some time ago I worked on calling cards. Generally they blocked 8xx calls because it was felt people would feel cheated if we charged for them, and there was no point in doing it for free using a premium service when they could make the free call from the phone they were using to call us.
There was also the issue that certain 8xx numbers were only supposed to work in certain areas. Now long distance is so cheap they are probably all national, but back then, a calling card call appeared to originate from where the card processing equipment was located, so the areas would be all messed up.
That issue also made me wonder about the legality of something British Telecom implemented, which allowed UK users to dial a US 8xx number. It warned them they would be charged for a call to the US, then put it through. I happened to be in London at the time and working for a non BT US carrier, so I called one of our 800 numbers and had the call traced. They were making it appear to originate in Phoenix, or somewhere in the SW. It got me to wondering whether an 8xx subscriber unable to do overseas business might claim wire fraud for being delivered collect calls he would never agree to accept. I never heard of that issue arising, so I guess anyone in such a situation who got enough of those calls to notice probably considered it cheap market research towards a future expansion.