AirWatch (MDM software) detected my iPhone 6 as jailbroken after it was jailbroken then restored. They had to add my device to an exception list. That could've been an AirWatch bug though.
Most likely a bug or some jailbreak system files lingering if you did a 'restore from backup' (iCloud or otherwise); nobody has demonstrated being able to detect a JB after doing a full restoring with iTunes and setting up as new.
Restoring from a backup absolutely leaves traces. The folders under /var/mobile/Library store configuration files for apps that are under /Applications[a]. As Cydia puts itself and other apps in here, it’s configuration files aren’t stored alongside them.[b] The consequence of this is that a backup backs up roughly the entire /var/mobile folder. So when a restore from backup is done, Cydia’s (and other apps’) config files are put back.
In theory, Apple could detect this (previously jailbroken state) when they plug in your device at the store to do diagnostics, but (at least 5 years ago) I’ve brought a few “restored from backup” devices in for service and they don’t say anything. I guess as long as it isn’t currently jailbroken, they don’t care.[c]
[a]: /Applications contains apps that come with the device and can’t be removed (such as Settings, etc.); Cydia installs itself and any apps you install through it into this folder. OTOH, apps installed through the App Store go under /var/mobile/Containers.
[b]: The reason being: pre-jailbreak, / is mounted read-only, but /var/mobile is read-write. So iOS works on the assumption that any app installed to /Applications can’t keep its config files with it, so they’re put in /var/mobile/Library.
[c]: Simply hiding the icons of Cydia and apps wouldn’t be enough to convince them as jailbreaking involves disabling a few daemons (the biggest is the OTA update checker; they don’t work well with a jailbroken device), so Apple’s diagnostics would probably show that some daemons aren’t running (that normally would be).