Sorry if this is a year late, but..... For other Canadians looking for DEM data checkout
http://www.geobase.ca/geobase/en/find.do?produit=cded click on either of the 2 maps at the top and zoom into your area to get the identifier or range of identifier's you want/need (basicaly a description at to where on the grid of maps you are looking). Then search for them in the first page for links to download (http or ftp) So far it seems like different versions dont matter, as long as you get the total coverage of your area.
Edit: Take those files .DEM and run them through "MicroDem" a free program that will open and patch together your dem files and can save as a .BIL to use with Redem.