Does it actually say that the mailbox is full, or just that you cannot leave a message at this time, with no reason given?
I had a customer with a PVMS (small) that had all incoming calls answered by the autoattendant. He had a phone in DND. If one of the VM ports is already in use when the call comes in, hits the other VM port for the AA, transfers to the DND station and back to the VM port to take a message, it happens so fast that the PVMS does not get the mode codes and cannot handle the call. It plays a message that you cannot leave a message now. Avaya tech support was aware of this when I called tech support, said that's just the way that one works. The solution was to NOT put the phone in DND, that way the call rings 3 times before coming back to the VM, the mode codes come in fine, and the call is handled properly.