I have an S5 with kitkat and it connects perfectly to my 2012 Highlander. I don't have entune, so maybe that's what's throwing it off. Does your car (I assume because it's a '15) have the entune stereo system?
And not for nothing, but you can complain on facebook all day, and it won't make a difference:
1) Every company, especially Toyota, caters to the iPhone, not Android. There are loads of problems that they couldn't care less about fixing for that reason
2) It's probably working for >99% of the customers, so they will do nothing to help you. Clearly they blamed the phone, Samsung will blame Toyota. It's a cycle you can't get out of.