I think the origin of that stereotype comes from the 19-nth century when Russians started to spend more time in Europe and subsequently Europeans started to visit Russia more often. So, Europeans saw an unaccustomed sight when the street clowns made a trained bear 'dance' while they played music. By that time, Europe was significantly stripped off of their forests, so they had no bears anymore. So, Europeans became astonished with a place where the bears 'run free' on the streets.