I'm having this problem too.  My iphone 4S was sitting 3 feet away from the M-cell last night and it didn't even act like it was aware.  I'd completed all the trouble shooting steps including have AT&T re-register my phone on the network before I saw this posting.

I realize the M-cell goes out and looks for updates each time it's powered back on after being off for more than 10 seconds but it would great if I knew what version it was on and when the AT&T regularly scheduled updates.  As it is, I cycle the power on it compulsively hoping this will be the time I get the jackpot.