I run into this about 30% of the time. A restart of my phone seems to "fix" it.
Atrix2 ICS 4.0.4
I have the same "no internet connection detected" problem when I am clearly online. No problem before but it has now gone on for several weeks. I was about to upgrade, but it seems pointless.