Solved!
The issue was that had sent to my collaborators the UUID finder App which apparently has a bug (at least on iOS 7 devices) because it gets the wrong uuid:
It does substitute in the first part of the UUID a series of letters "F" and change the rest of the uuid:
UUID / UDID / UID:
FFFFFFFFrestofuuid(incorrect)
The safest way to get the correct uuid is to copy it directly using iTunes. One you have the correct ad hoc distribution certificate (with the right uuid) then send it to the tester and ask to reinstall (by dragging and dropping it on iTunes and then Synchronizing or by sending it via email and opening the mail from the device - which will prompt the user to an installation process). To check if it is installed on the testers device in the general settings menu.
Notes: I sent the UUID finder App a couple of weeks ago (as of 23 December 2013), so the current version of UUID finder may be working correctly. Double check in case you are in doubt. EDIT: API deprecated, see Deprecated UIDevice Methods - Apple Developer