I have similar observation. After first boot everything is ok. Phone connects perfectly. Next I reboot phone and I can see that phone is connected for 1s not connected for ~20s (looped). What I noticed: additionally Airplane mode switches on and off. All of this without any touch to phone.
I observed this in every KK ROM I tested. There were a few times that phone worked properly after restart.
I always install new ROM on SS Slot 2 that is wiped (system, data, cache, dalvik) before installation.
Today I installed latest MoKee nightly (02.19) - result as described above.