Just out of curiosity....Have you ever put a Volt meter on the power line that feeds your PB??
I wonder, if what is happening is that when you start the car, the voltage drops just enough to confuse the PB and cause it to loose sync. You might be able to have someone watch the red light and you crank the car up, then again, the red light might not go out all the wya, it may just dim for a second.
You could try putting a capacitor on the power line to ground. like a smaller version of a car stereo capacitor. that should hold the line voltage up during cranking and add a bit of filtering to your unit. 5-10,000Mfd at 16 volts should be enough. make sure to connected it with the correct polarity. and remember, these units store electricity, they are still charged with 12volts and substantial power when there disconnected. a 12 volt light bulb works well to discharge them.
Radio Shack and other electronics stores sell these. should be less then $5
Let us know what happens
Zc