From your log looks like that you are connecting against a CRM Online instance that is still using Windows Live Id
authentication, the DeviceidManager.cs
is a big clue but not a complete proof.
Windows Live Id
authentication still needs the device credentials, this is an issue on Azure hosted apps.
Try to use the simplified connection, you can find an example here: