I had both 'Login Security Solution' and 'Better WP Security'plugins installed on our multi site, both plugins were installed and activated at the network level.
There was a conflict where Login Security Solution required a strong password (as expected) but would not accept any password, no matter how strong.
Deactivating Better WP Security removed this problem, but I'd rather have it activated.
Any ideas why this might have happened? I had both plugins installed on a standalone WordPress site without any issues.