Thanks for the constructive suggestions about alternatives - the Sobeys MC looks like an excellent backup.

As for CIBC Visa's Customer Service, I just got off the phone with them, and it wasn't easy. It will take 3 or 4 business days for a new card. The security agent could not handle an "incentive to stay with Visa" request and put me through to Customer Service, where the agent just wanted at argue with me, and as the conversation escalated to a shouting match (he would not listen and at one stage said that security could have handled it). So I did the inevitable and asked for a supervisor, with whom I did have a rational conversation, was offered some meager incentive/compensation miles, and strongly suggested (as per the discussion on this thread), that CIBC Visa would do well to improve its ability to quickly handle a compromised card situation.

I am also going to get an AMEX gold card and see how it goes. Their annual fee appears to be the same as Visa and the incentive miles worth a try.