This is incorrect, at least in Canada.
Canada is a one party consent jurisdiction as far as criminal liability goes. In other words, you can secretly record any phonecall or live conversation to which you are a party. (You cannot, however, secretly record third parties, even if you own the phone. eg: your wife and her lover)
The reason businesses in Canada inform you is that under PIPEDA, because they are businesses, they are subject to certain (civil) privacy requirements.