One of the first problems I see is that supposing you are a webmaster of a site and 5 companies have approached you to display a fuzzed up logo in you captcha.

Now since there aren't infinite string variations you are left with randomly displaying only 5 kinds of verification phrases which are easier to manipulate once you take into account that colors associated with brand logos are easier to recognize than actual alphanumeric strings displayed as images.

Also since captcha's are mostly for the benefit of the website/webmaster, they are seen in an annoying light by consumers who actually use the site. And that is a strict no-no to any marketing strategy.

Advertisers don't want to associate their brands with annoyance and inconvenience.

I dont buy that. Theres plenty of intrusive advertisement on the internet (popup advertisement, advertisement that blocks the page until you close it, advertisement pages that appear when you click a link and then must click "skip this ad" or similar).

There is brand-safe advertising, and then there is popup-advertising. Hardly the same thing.

Sometimes God hates ideas so much that he intervenes to make sure that they never ever happen. This is one of them.

More importantly, why hasn't http://www.thepcspy.com/kittenauth taken off?

This is more practical (and cuter) than using brand-logos.. Pictures of kittens and other animals are easy to find, whereas getting a wide enough range of companies willing to let you use their logos will be far more difficult.. It would be like having a captcha where there are only 5 possible strings to enter..

There are patents involved, maybe the licensing costs were too high?

I've been asked to work on something similar, but my lazy/distracted ass hasn't gotten around to it yet.