Well, some people get a "call forwarding active" message every time they do a call. I read a lot about this topic and there are also some threads about it in here.
To sum up:
It's not a bug, it indicates that your calls are being forwarded either to your mailbox or an "caller unavailable" message by your provider.
Some people made the message disappear by forwarding all calls to another number, and then enabling again (not sure if mailbox still works).
Activating "call waiting" lets the message disappear (since incoming calls are not forwarded anymore).
However, there is a simple way to hide this message:
Get the file com.apple.carrier.plist found at /var/root/Library/Preferences/ and edit the key ShowCallForwarding to be <false/>. Reboot! There you go, your Mailbox works and you don't get that annoying message anymore
Update:
There are two settings in com.apple.carrier.plist:
ShowCallForwarding: Message shown on outgoing calls, if your number is beeing forwarded.
ShowCallForwarded: Message shown on incoming calls, if caller has been forwarded to you.