I have shadowed two physicians so far this week, and the new privacy laws have not been a problem.
The first doctor is a pediatric surgeon, and he approached the families with me present to ask them if it would be ok for me to observe the surgery (all consented). He would explain that I was starting medical school (though I am sure premed works too) and was there to shadow him. In his office visits, he brought me in the room with him and asked if the patient was ok with my observing and only one person said no. As far as hearing names, seeing records, etc, these were all in plain site the entire time. Therefore, I chose to keep them to myself (honestly, I have forgotten them all) as a matter of privacy and discretion.
The second doctor is a gastroenterologist, and he brought me into the rooms for consultations, introducing me as a beginning medical student. Though he did not ask the patient if they would refuse me, all seemed undisturbed by my presence.
Overall, each experience was excellent, and I feel confident that I did not disturb the privacy of any patient involved. All knew I was there, and those who had a problem with it could voice their problem. In fact, most told me good luck and were eager to share their medical histories with me.
Conclusion, I do not think privacy laws have caused too many problems for shadowing so there is no reason to hesitate calling up a physician about shadowing. In the end, you learn quite a bit about lifestyles and doctor-patient interaction. Medicine in practice is quite different than in one's imagination and the idealism you might pick up in books. The only way to see that is to shadow.