I totally missed this with a client - thanks Phil for pointing this out.
By default Ex UM saves Vmsg in WMA format which does not play on Blackberries.
set-UMMailbox alias -CallAnsweringAudioCodec GSM
will change the Vmsg to WAV format.
Out smart PSS folks documented this way back in June 2008 - I just missed it. :(