Firebase dynamic links were not working for us (on iOS9 where they use universal links) due to a problem in Firebase's assumptions during setup. Here's how we fixed the problem on our app:
Firebase asks for your "Team ID" when adding your iOS app to Firebase Console Project Settings, and it assumes that your unique app ID will be in the format TeamID.com.foo.bar
However, in our case, that was NOT our unique app ID. When I looked at our provisioning profile (on developer.apple.com I found our provisioning profile and clicked "edit"), I saw that our unique app ID was actually SomethingElse.com.foo.bar
I had to go into Firebase Console and enter that "SomethingElse" in the spot where it asked for Team ID, even though that was NOT our team ID. Once I made that change, Firebase Dynamic Links started working correctly.
It appears Firebase is making an assumption that your unique app ID will always start with your Team ID, which is apparently not always the case.
Note that changing your Team ID can take a significant amount of time to take effect. You can see that the change has happened by checking the appropriate link for your app_id (https://app_id.app.goo.gl/apple-app-site-association).