I had this problem as well, soon after I ran a mass of updates. None of the forums were very helpful, so I had to figure it out myself... so here it goes:
Next time the star appears, click the ad and see which app name appears in the upper left-hand corner (as it takes you to the Market to view the app it's advertising).
For me, the app was Easy Filter. I deleted it and read the other reviews, and the other users were equally peeved. I think the ad service is AirPush or something... some of the free apps are using it now to generate income, I'm sure.
I hope you find this useful. I'm so glad to be done with those darn ads!