I have already reported this bug in the public forum:

https://social.msdn.microsoft.com/Forums/en-US/outlookdev/thread/e14f4e90-5913-4df9-9a35-51d9432a3683/

And found other reports on the Stack Overflow:

http://stackoverflow.com/questions/28238849/contacts-are-getting-created-only-in-root-folder/28239672
http://stackoverflow.com/questions/28975976/creating-contact-in-folder-with-office-365-rest-api

We can't add contacts to specific folders. We receive a success answer from the API, but the contact is always added to the root folder.
It was already confirmed by others. Please, could you take a look and fix it?

Thanks