Once they start messing with that, legal or not, I feel there will be a huge political backlash. While the confrontation will be fascinating to watch, I believe the "stop messing with the cell phone" party will win.
It really depends on if you can prove malicious intent. I know in the back of Wal Mart, for example, my cell reception is terrible. There are metal walls everywhere, thick metal shelves, and the back of the store is made of concrete and rebar. When I go into a store, I really expect my cell service to drop out. I expect a lot of people have the same expectation.