I have had similar issues with my Motorla Droid. Angry Birds runs extremely choppy, it's only smooth once in a blue moon. I think it's the ads but I'm not 100%. I'm waiting for the ad free version to see. My wife also has a weird problem, sometimes Angry Birds will completely disappear from her tray and she will have to restart her phone a couple times for it to reappear. It's completely random and it's only Angry Birds.
The game is GREAT but I am one of the few people that find this release to be the pits. I thought they made us wait so they could optimize the game and make sure everything ran smoothly. Me and my wife have yet to have Angry Birds run smoothly. She downloaded from the Market, I downloaded from getjar so it's either the ads or the programming. I still love the game though.