Look no further! Here's your problem and I know because I've run into this countless times myself.
Not only will you have to upgrade the voice mail system, you'll also have to upgrade the telephone system to at least 6.1 or higher (might as well go for 7.1) with a release 2 NVRAM pack just to interface correctly with PRI!!!
This is a well known issue that has been discussed to death in this column over the last few years!
Do not be at all surprised if you have multitude of weird little problems that seem totally unrelated to PRI, until you correct that glaring software mismatch!
Phonehed in Dallas