What firmware is installed on those 256mb machines you tested and did they have to be downgraded from 3.41 or higher?
My theory is that FW3.41 is part of the problem.
I can't test this but maybe you can:
Remarry a drive on a 256mb which was never on a firmware 3.41 or higher
Remarry a drive on a 256mb which was downgraded from 3.41 or higher
from the manual:
Renewing the AACS encryption key
You may have to renew the AACS encryption key to play content such as movies on commercially available BD video software (BD-ROM). If a message indicating that the encryption key needs to be renewed is displayed, update the system software to the latest version. The encryption key will then be automatically renewed.
AACS (Advanced Access Content System) is a copyright-protection technology that is used on Blu-ray Discs. The copyrighted content is protected by setting an encryption key on both the disc and the device used to play the disc.
An AACS encryption key expires in 12 to 18 months and must be renewed. There may also be other times when the key has to be renewed.