The Nova Scotians.
“Pray, sir,' said one of my fellow-passengers, `can you tell me the reason why the Nova Scotians are called ‘Blue-noses’?'”
“ `It is the name of a potato,' said I, `which they produce in the greatest perfection, and boast to be the best in the world. The Americans have, in consequence, given them the nickname of Blue Noses. ' ” —Haliburton: Sam Slick.
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Blue-noses from Infoplease: