Well it certainly has something to do with the mailbox itself.
It won't have anything to do with the rerouting programming.
I would think that the problem is due to something in the extension field of the mailbox or perhaps the mailbox type.
1st be sure that you can dial the extension number from any phone and that there is no delay between when you dial the last digit and the time it rings.
If there is a delay then you have a digit conflict you will have to resolve.
2nd, be sure that the extension field matches the actual extension of the phone.
3rd, be sure that the mailbox type is correct. It will need to be set to "mailbox".
4th, if the above doesn't resolve it then verify that the phones are in the same tenant as the rest of your phones. I'll assume yes since you can dial it via the AA when there isn't a mailbox.
Ralph