I have the exact same problem
I have a GSM Samsung Galaxy Nexus on Vodafone, and within about 2 minutes of the screen sleeping, it loses connection to the network. When awakened, it will re-establish the connection within 5 seconds or so, but it is intensely irritating as I have missed lots of phone calls with this bug.
It has occurred on both my 4.0.2 patched to 4.0.4 and a clean install of 4.0.4 from google's website
I am about to revert back to 4.0.2, but if anyone can fix it in the meantime I would be eternally grateful.
-------------------------------- UPDATE ---------------------------------------------
I concur with warhummer. After rooting my Nexus again after the 4.0.4 update, and installing CPU Tuner from the Market place, I increased the minimum CPU speed to 700mhz (up from 350mhz) and it appears to be keeping its signal now. This would also tally with the fact that while my Nexus was doing things in the background it would maintain signal, but as soon as it was idle, within a few minutes the signal would die.
--------------------------------------------------------------------------------------
|