No, they're illegal because FCC regulations specifically ban any device that interferes with other transmissions, _especially_ transmissions over reserved frequencies. By the letter of the law, this is actually kind of a gray area, IMO. I think if it does get nailed down, it will only be because the cell phone companies retaliate against users because of some license agreement loop-hole. I'm not sure how the FCC actually stands on the issue of in-your-home, but as long as the device doesn't transmit a disruptive signal outside of the house, I think the MagicJack people are in the right here.
(full disclosure: I'm not a lawyer, but an amateur radio enthusiast - so I've read a fair bit about the issue)