Issue with both recording and leaving messages

You need a G.729 codec and any licences it requires, or you should disable the use of G.729 in your system.

However, as the last posting says, it is questionable why you should want G.729. In particular, the trend it to increase telephony voice quality, rather than to reduce bit rate at the cost of quality. Even low wage call centres are probably tending towards that now.