On my 3Gs I took those steps and when I clicked the "show my caller ID" button it took me to a page that took a second or 2 to load, then gave me the toggle to switch it off. Did you not get the toggle? I can switch it on and off.
I think that is your problem. Often times employers don't want their employees making anonymous calls to people, either within the company or out of it. I think you're stuck bud. You can check with At&t and see though.