I had this problem for the past two months and it too drove me crazy. I finally got steered in the right direction in a couple other threads.
Go to Settings>Application>Application manager>More>Show system apps>Samsung keyboard>Permissions and deselect "Contacts"
Then go to Language and...