Ok, after a great many hours spent debugging and reloading software both issues have been resolved...
Turns out, the 'Expired Certificate' problem is NOT CONNECTED with the 'calls failing on UMA' problem. They happened to occur at about the same time which is why I figured they were connected.
Here's a detailed dump on what happened and how it was fixed. Hopefully it will help you all in case you run into the same issues:
'Expired Certificate' Problem
--------------------------------
The support rep at RIM accepted the fact that this problem was caused because one of their certificate servers was malfunctioning. As I'd said in my post yesterday, we tried removing the battery and hitting 'Continue' several times but that didn't help. The idea was to get the BB to clear away part of its memory that was holding on to the expired certificate and replace it with the new one. But that wasn't working.
Eventually, the rep said the only way to fix the issue was to reload firmware on my BB. Even though I had the latest 4.2.2.180 firmware on my BB it was not going to be enough to simply 'Wipe Handheld'. So I downloaded the latest firmware from
Unsupported Browser and reloaded it onto my BB.
(All in all a painful process because halfway into the firmware upgrade I get a '507' error on my BB. Disconnecting/reconnecting my BB seemed to make the problem go away).
'Calls Failing on UMA' Problem
----------------------------------
This problem was caused due to Verizon's latest Actiontec MI424WR router. They apparently came and replaced my router when I was away on business last week. But the SSID was the same so I didn't realize the router had been replaced.
So, for some unknown reason the newest Action router running the same firmware as the old one doesn't allow UMA calls. It's possible the problem is due to port forwarding not setup correctly. I will look into it on the weekend.
Meanwhile, to get things working, I've daisy-chained my old Linksys router to the Actiontec. My BB connects to the Linksys SSID and UMA calls now work fine. (Just make sure the Gateway setting on the Linksys reflects the IP of the Actiontec and you're good to go).