Thanks guys. We have spent most of the day getting to the bottom of this problem and it turns out that the new call forwarding feature was having a negative impact on our voicemail system:
See Tony's post:
http://forum.voxalot.com/showthread.php?t=1177
We have since turned of call forwarding to fixed line numbers (only URI and voicemail forwarding are currently active). Please check that voicemail is working as expected.
We apologise for any inconveniences caused.