I wasn’t sure whether to post this or not, but I didn’t want anyone else to waste the time I did tracking this down. If you are listening to the voicemail greeting and press ‘*’ to escape to voicemail menu, this doesn’t work if the underlying engine is Asterisk 1.6. This is a bug in the VoiceMail application (a regression introduced somewhere between 1.4 and 1.6). I have opened a bug on the asterisk bug tracker and have a one-line fix if anyone needs it.
Fix submitted and should be in next 1.6 build.