I've had Sony, Nokia, Moto and LG phones on AT&T/Cingular over the last 10 years and this has been a problem on all of them, along with "missed calls" showing up hours later. I've noticed it less with the iPhone, but it's always the important calls/voicemails that don't come thru properly, of course.