Maybe I'm weird, but I believe in the theory that (all else equal) it's good for business to minimize how much your users hate your product/service.

In other words, users dislike the feeling of not knowing whether things are ads. I can't see any real downside to labeling them, so you're better off doing it so you don't drive users away.