Android - Adding a new account to Gmail/Youtube shows a Password Error

At least for me, it was actually the device password - used to unlock the phone. So basically it asks for the device password when you try to add a new Google account for some reason. I formatted my phone thinking something else was the issue - but if you enter the device password, it then asks for the account name as normal.