As a whole, people in ASOIAF are surprisingly tolerant of other religions. Is there a basis for this, or are the people in the Seven Kingdoms too busy killing people over other things to care?
Very good question. I think understanding the background is essential to give an answer. In the following chronology, the Year 1 corresponds to the invasion of Aegon the Conqueror.
Before -12 000: Age of Dawn : basically, only Children of the Forest and giants lived in Westeros. Their religion is the Old Gods.
-12 000: The First Men come into Westeros, they start a war with the children of the forest, which will last for 2 000 years.
-10 000: The war is ended by a pact. The pact sets the territory of each people : the children get the forests and the men get the rest. The signature of the pact sets the beginning of the Age of Heroes. The Old Gods religions is spread among the Men, the Age of Heroes begins. During the Age of Heroes, the main Houses appear (Stark, Lannister..)
-8 000: The Longest Night begins It is called the longest night because winter lasted for a whole generation. The Others appear during this winter. Men and Children of the forest ally themselves. Others almost win the war but a hero appear : Azhor Ahai. In short, he discovers obsidian stone and had a magic sword so he was really powerful. After the war, Bran the Builder builds the Wall and the Night's Watch appear. The Free Folks are the descendent of the First Men who happened to live North of the Wall when it was built.
Note that at this time, the religion is still the Old Gods' one.
-6 000: the Andals invade Westeros: this is the key event to understand to answer the question. The Andals come from the East and invade Westeros. They bring the Faith of the Seven and spread the Faith of the Seven. But they don't manage to conquer the North quickly because of the powerful fortress Moat Cailin... So the North keeps its religion longer. So the Old Gods religion is stronger in the North.
The events after this one are not really relevant, just note that Aegon the Conqueror led a war and united the seven realms during Year 1, but didn't really care much about religion... he had dragons. He and the rest of the Targaryens didn't originally believe in the Seven. He converted during his invasion to gain the support of the High Septon and the Faith Militant (Thanks to SystemDown's comment for this part). You may not know what is the Faith Militant. This is revealed in A Feast for Crows. Basically, it is composed of people who swear to fight for the Faith.
I think when Aegon conquered the North, one condition of Torrhen Stark's (the last King in the North, at least before Robb) surrending was that his people could keep their gods.
Also, TheMathemagician's comment makes sense : the Faith doesn't hold much power in asoiaf. The king doesn't care which gods you have, as long as you pay your taxes.
The crusade against polytheism in our own history originated not with Christ, but with Rome. When Rome conquered a people, they would leave the priesthood intact, and sometimes even some members of the previous royal family. As the military grasp of Rome slackened, there was a fear that those intact priesthoods would anoint some survivor of the old royal families as king, and rebel against Rome. A militant monotheism was useful to Rome to suppress these old priesthoods. The world of A Song of Ice and Fire seems not to have had this kind of history.