It's doubtful that the greeting has anything to do with it. This issue could be complex (especially if it's a Connection cluster and/or there are firewalls between the phone and Connection) so you might be better off getting TAC to help troubleshoot.
But to narrow down the issue, you should try to figure out if it's the phone midlet/firmware or something on Connection (or possibly something in the middle). To do that, you need to take a look at the phone logs (see
http://www.cisco.com/en/US/docs/voice_ip_comm/cupa/visual_voicemail/7.0/english/install/guide/troubleshooting.html#wp1058327 ) and the VMWS traces in Connection (turn on all levels of the VMWS micro trace in Connection Serviceability; traces will be written to cuc/diag_Tomcat_*).
Basically, when you press a button on the phone, the midlet acts like a web browser and should contact Connection to perform the login. There are obviously a lot of different things that can happen due to caching and whether or not there was response received (especially if there is failover involved), but essentially it's important to make sure this phone->Connection communication is still happening. Of course, the Midlet is at the mercy of the phone firmware for accomplishing this, so the firmware version (and phone type) is very important and can impact things.
