And another update, 7/25. The patch only partially worked. The leads were making their way into Marketo, but Marketo hasn't been able to pass the leads into their appropriate instances.
According to support it seems like the issue is on Marketo's side of the house, not FB, and it's affecting a lot of Marketo customers, not just a few of us.
Lead ads are now working for us across all clients - finally! We have been told that "the issue was not directly affected by the changes made on Facebook's side, but rather it was an an error handling issue with canceled Marketo subscriptions that still had Lead Ad campaigns active that caused the backlog". The cynic in me wonders how it was timed exactly the same day as the new Facebook API release, but it's probably just coincidence...? Who knows. The good thing is that it's fixed, and we don't have to do manual Lead Ad data uploads multiple times a day across multiple clients!