Call the airline you're flying on and make sure you can bring them on as carry-on. Get someone at that office to fax or mail you a signed letter from a supervisor saying that you are allowed to bring then as carry-on and make sure you have that letter on you at all times at the airport.
I've read too many stories of people getting to the gate only to have to throw their turtles/hermit crabs in the trash because they aren't allowed on board or because the employees are dumb and won't double-check the regulations. I don't know how much better the Canadian airlines are, though I have a feeling they rock compared the US.

Still, better to be prepared!
And yes, as long as they are in the cabin with you the crabs will be safe. As checked luggage.... there's always the risk of them freezing on the tarmac or not being pressurized correctly in the hold.