We figured out our problem, and I am posting my answer here so that others may find it helpful.
The problem is really a UX problem with Keychain Access. Let me back up and give a little context: when you create a distribution certificate with Apple, you create it based on a PRIVATE KEY and App-based permissions.
In Keychain Access, the distribution certificate is listed as a child below the name of the private key that it was created from. Here's the catch: When you use the search box in Keychain access (in my case we were typing in "Roomer" because that's the name on our distribution certificate), it won't look for a certificate with that name, it will look for a certificate attached to a private key for that name.
So my colleague had create a distribution certificate based on a private key that was named "Jorge Davila" (his name), even though the distribution certificate was named "iPhone Distribution: Roomer Inc."
When he searched for "Roomer" in Keychain Access, the correct one was NOT displayed in the search results because the key this certificate was created from was named "Jorge Davila" not "Roomer". Thus, he was exporting the wrong certificate and didn't realize because there were others (some expired) with that name.
Here's how the correct one looks:
This is a relatively nuanced problem with the UX of Keychain Access and the fact that the search tool doesn't give you the results you expect it to. I am posting this answer in the hope that others may find it useful.