I've discovered a variation of the problem tested in tests/Validator/ForeignKeysTestCase.php. This happens when you synchronizeWithArray and a foreign relation is set - isValid will trigger the isnull validator.
This is probably better explained through two new test cases. I've included them below. The first test case passes. However, the second test case (testSynchronizedForeignKeyIsValidIfForeignRelationIsSet) fails.
I've discovered a workaround, if you reassign the value it will work.
A quick and likely terrible (or wrong?) fix is to have the synchronizeWithArray function do it for you. I've attached a patch does just that.