I'm going to write a guide about this - this is the third time I've answered this one today.
Bluetooth isn't a standard, it's a "these are the things available - write whatever functions you like" thing. so some companies give you a contacts profile that's too different from another manufacturer's contacts profile for them to talk to each other.
The S4 isn't some Chinese knockoff that only 5 people own, so car manufacturers should write profiles that will talk to it. Go to your Honda dealer's service department and see if they have any service notices or updates for the problem. Or if one of them has an S4 and knows how to make contacts work with their electronics.