Hi,
I faced this problem before. If you are using latest android version like 4.2, you need to use latest adb binary to connect to phone.
This ADB will send a RSA key to phone from PC which is unique for every PC, which you should accept connection just like you do for a bluetooth connection...