I have t-mo version, but the issue is mostly same - my Mazda says pairing failed after kitkat update. And actually it's still possible to connect phone to a car (even if that is not well paired). But only using one of profiles - phone or media, but not both at the same time (that worked flawlessly on JB) and each time that's random - today i was able to use only media, but not as phone.
I have S3 which is still on JB and it's still works pretty well with a same car.
I tried resetting, re-uploading, but issue is still there.