This was still occurring today so I opened up a ticket. Just got a call back that this has been escalated to RIM's network team, which no doubt is scurrying to find which server(s) has the outdated cert loaded on it.
No ETA, but I guess with RIM admitting there is a problem is a good first step to recovery.