What did you search for? I looked for just baa baa sheep (no quotes) and all of them that came up had the black in the middle.
It does look like there was an instance, in the UK last year, where a parents group tried to replace the "black" with "rainbow."
http://women.timesonline.co.uk/tol/life_and_style/women/families/article738220.ece
http://news.bbc.co.uk/2/hi/uk_news/education/4782856.stm
I guess I don't understand the origin of the song and I'm sure it is naive to think that the use of "black" in the verse is just a result of black sheep being a naturally occurring phenomenon, but it really doesn't seem like a racist rant. In fact, since I assume it comes from England, I'd think it had something to do with class or enclosures since sheep themselves were hardly an a-political topic. But I can't quite get that out of the rhyme just by reading it.
Either way, this seems like a fairly strange exclusion--or one based wholly on a misunderstanding. It would make more sense to just stop singing the rhyme altogether since it obviously has very little to do with the average kid today.
s