The law dates back to the days when cell phone tranmissions were analog and could be picked up with a consumer-grade police scanner. As I recall, it was passed soon after an incident where a congressman's conversation with his mistress was picked up and publicized, but I don't have a authoritative source for that.
Even with modern phones being digital and encrypted, the law remains in effect.
18 U.S.C. 2512 may be older but I wonder why such a regulation would have been issued so recently.
Also if this regulation is intended to implement 18 U.S.C. 2512 it appears to be broader in scope than that law. The law only prohibits devices that are "primarily useful for the purpose of the surreptitious interception of wire, oral, or electronic communications". The regulation on the other hand restricts scanners that are capable of receiving such communications. I don't see how a broadband scanner that includes cell phone frequencies along with other bands could be considered to be "primarily useful" for intercepting cell phone communications.
But in general, "you can't listen to this frequency" is completely crazy; "listen all you like but you won't get anything useful" makes more sense (along with "don't broadcast on this frequency above this power without a license").
EDIT: I think this happened in 1994 - google "cell blocked" scanner and you'll find stuff on it.
Edit Again: Here's a QRZ thread on it: http://forums.qrz.com/index.php?threads/why-are-ham-radios-s...
Is this true ? I've never heard of the FCC restricting receivers before. You don't need a license to buy or operate a HAM receiver.