Sorry for your aggravation. That is such a pain. Sometimes these cancellations seem to be part of a bigger event and sometimes individual incidents. We did have a situation where it appears a store clerk was able to copy our debit card during a transaction and within 2 hours, someone attempted to use it for a four figure purchase across the country in the same store chain. The bank caught it (as DH could not have traveled 3,000 miles in an hour) and issued a new card.
Our local law enforcement emphasized how they avoided debit cards in retail and online transactions as they are easily compromised and allow for direct account access, as opposed to credit cards. I have reduced my use of them after this event, but one needs access to cash even if other cards are used for retail commerce.
Good luck and glad you have an alternative way to proceed.