I've had 2 brand new out-of-the-box 7942's do this on me now.
I configure the phone, extension, user, and voicemailbox.
When I hit the Message button, the "1. Voice Mail " option is grayed out. If I hit 1 anyways, it says "that key is not active here"
On the first phone this happened, Cisco replaced the phone. I can't believe I'd have 2 new phones fail the same way.
I've got 2 more 7942's on a CME router at a different branch in this network that have no issues.
I did have to make sure 8.5.4 firmware and not 9.x is in the tftp server.