I have just noticed that some user's do not appear on our Self-Service Portal in a User Picker that should have all users in it (no constraints).
It appears that an entire OU is omitted from the results, however the users appear in Configuration Items -> Users. From this, I don't believe it to be an issue with the AD Connector, more an issue with the Self Service Portal.
There were no criteria, and it was still not working. Since then, I have added "OU contains 'Users'" as we have other OUs such as "Resources" which contains service accounts and such, that I don't want synced.
So currently, there is a constraint on the OU, but this has not affected this issue. All users within this OU are still not appearing :(