After installing trixbox and updating the system I could not add new extensions using FreePBX.
Although the solution is quite easy, it took some time to find out. So here it is (I found it in the FreePBX-Forum):
Simply delete all contents in the files /etc/asterisk/vm_general.inc and /etc/asterisk/vm_email.inc. Then perform an amportal restart and everything works fine again.