lenovo P780 & bluetooth problem

I'm havig the strangest problem with my new smartphone: in some areas (central Israel), after dialing a phone call with car bluetooth speaker device, I “fall off” the network and after few seconds the phone reconnects. It' terribly anoying especially since it hardly happen in the northren part of Israel.

When I make the same call (same destination from same location) with the phone without the car kit, there is no problem.

Sometimes the same problem appears when I try to dial, before it rings in the destination.

Other problem, probably related to it is the sound quality- many times the other side claim he can hardly hear me.

When receiving calls, there are no problems (or, at least, very rare)

I tried several attamps to find the problem but can't find a clue of how to solve it, how to focus the issue and not even what is the source of the problem.

My provider claims that since I reconnect almost immidiatly (and didn't have this issue in an old device) shows that the problem is with the device and not with the network.

Tests done:
As pointed out it happens only in some areas and not everywhere
I tried several car bluetooth kits, the problem remains
Using an old device (Galaxy S)- there is no problem
Tried SIM card of another provider- no problem
Tried to change Modem software- didn't help

My configuration
Device: Lenovo P780
Android 4.2.1

Ideas? Hints?
Other places where I might find answeres?

Thanks