We haven't been able to recreate the problem, since we don't have a Canadian address and credit card we can use. However, one customer forwarded the error page and url to us. The url is as follows:
checkout_failure.php?shipping=fail
so it looks like there might be a problem with the shipping api. Any ideas?