My wife got an SE today, She restored from back up and same thing as you, links worked fine initially but once it had finished installing apps it now does not work again. She didn't even have booking.com installed. Not a great start for a new device.
It works for me
I haven't installed some apps, but I don't think they're the cause of the linksgate...I don't remember which apps but, for example, I haven't Booking.com also on the iPad Mini.
The build is the same, iPad Mini 4 on front (damn looks yellow
) iPad Air 2 on background.
At the moment all the links between apps (mail, etc) are working. But I also haven't rebooted.
Oh, one important thing: since I haven't any apps .ipa files saved on my iMac (where is the backup), all the apps installed are the last release. Because, after restoring the backup, all the -not Apple- apps are only black icons. And I downloaded all again from the Apple Store. Maybe for that is working
maybe there was an app (also Wikipedia could be the cause) who "started" the corruption of the Universal Links service and now, that some apps went update in the last 2/3 days, have fixed the bug..???
Just suppositions meh...I don't know!
If you want to try, make a backup of the iPhone/iPad via cable/wifi (not iCloud), and then move all the apps .ipa files (inside the iTunes folder) to another location and then restore the backup. After you will see all the apps on your device but they aren't usable (black/obscured icon), open the App Store and download every app again (just tap the cloud icon) and you will download the last release MAYBE without incurring in the links gate... (Because iOS doesn't backup the root files, I mean it only backups the /Home folder, not the /bin, /usr folders and the corrupted Universal Linking file is somewhere in the root directory... You need to know the UNIX OS to understand what I'm saying)
Good luck!