With the vast number of wars, conquests, skirmishes, and the occasional flat out slaughter that punctuates the Dark Ages, people who are different/foreign are viewed with suspicion. But the English have a special place in their heart for a few peoples in particular:
The Crusades are all about reclaiming the Holy Land from the Saracens, who today are known as Muslims. The history is long and bloody, and people likely know someone who was killed by a Saracen.
Durham's angry northern neighbors who in the past have frequently brought bloodshed in their wake. See The Kingdom of Alba (Scotland) for more information on Scotland.
Oddly, as often as English Kings are related to French Kings, they keep going to war with each other. The French were considered untrustworthy cowards at best by the common folk.
Wandering travelers with roots in central Asia. The Romani people have barely begun showing up in Europe at this time. The appearance of of one of these exotic foreigners in the North of England is always strange. In later years, these people become known as "gypsies" as they make their way to England in larger numbers. The term "gypsy," once it does come into use is generally considered a pejorative that would be applied to the Romani people by outsiders; it is not a term that a self-respecting Romani would use to refer to themselves or their friends.