TORONTO—When Nicholos Billard's employer at an Ontario construction company gave him eight newly printed Canadian $100 bills as a Christmas bonus in 2011, he tossed them in an empty coffee can. The next morning, they were shriveled—by the heat of a nearby radiator, says his mother, who made local headlines when she tried to get the bills replaced. Canada started rolling out new, polymer-based $100 bills two years ago, followed by 50s and then, last November, 20s. The money—slick like a sheet of plastic, hard to fold and partly transparent—is more difficult to counterfeit than Canada's old paper-and-cotton bills. Australia and New Zealand have used similar, plasticized notes for years. The U.S. has no plans to introduce them. They've been a hard sell here so far, forcing the central bank to defend them against a growing list of allegations: They don't work in vending machines; they clump together; they melt. "I avoid getting those bills if I can," says Mr. Billard's mother, Mona. While the serial numbers on her son's bills were still legible, several banks refused to replace them, she said. Finally, last summer, the Bank of Canada, the central bank, exchanged them.