Well there is a corrolation of PRLs and message counts. 60711 will not give you an accurate message count on your phone. I installed 60613 and I get exact count of voicemails. 60612 works also. So if you are having trouble with this, try 60613, and it should resolve it, if your tower supports it.
Weird. I've had 60711 since it came out and have done several ROM updates and always re-updated to 60711 and never had this issue. But glad you got it fixed.