A) Labeling an advertisement is not counter-intuitive because, by this time, everybody on the web knows what a banner ad looks like. Also, tricking a user to click on an ad by hiding its label is worse. If a user clicks on an ad, but don't realize that it is an ad, then their option of the ad and associated material will be negative. As a Digg user, I can differentiate between a paid and unpaid link on Digg, and I usually avoid the paid ones. Even if some users are tricked into click the ad, the number of hits does not mean much if the bounce rate is also very high.
B) The simple answer is that most of the time nobody looks at the small advertisement header. That is why you get errors.
The reason why most advertisers put the "advertisement" label at the bottom is because they want users to look first at the ad, then at the label. Ultimately, they want users to click on the ad before they notice that it is an ad.
However, users have adapted to this trick by simply ignoring them. It's called "banner blindness," and you can find more information on it here: http://www.useit.com/alertbox/banner-blindness.html
Basically, people know what ads look like, so they skip anything that looks like one and continue reading about whatever content the page has to offer. Even non-ad content will also be skipped over if it looks like an ad.
My advice would to be to follow the design of the site, and stick with consistency. Continue to place the ad heading at the top because placing the ad label at the top or the bottom will not affect the function of the ad.