Cingular thinks this is an "infinitesimally small problem" for them.
How are sites such as Locatecell getting their information? They could be purchasing it from insiders, they are no doubt using "pretexting" (social engineering) to persuade customer support representatives to give them the information, or gaining access to customer account information via the web (Verizon Wireless had another major security hole in their online billing system last year, similar to one in 2001 which they took two weeks to act upon).
Whichever mechanisms are used, it is clear that privacy is being violated and likely that laws are being broken, yet there seems to be little visible interest on the part of the telephone companies in going after the criminals--perhaps because doing so might expose how poorly they are securing the information.
The Electronic Privacy Information Center (EPIC) has a good collection of material on this issue here. (Updated January 9: They filed a case against Bestpeoplesearch.com, which admits to using "pretexting" as their method to obtain the information.)
(Thanks to cowmix for bringing this to my attention.)