Hi Sweetpeach,
On the letter itself, is it addressed to you and yer better half by name? if not, treat it as suspicious. There are some outfits out there that purport to be legitimate and ask for details etc etc - but are actually fraudsters.
Assuming that is genuinely is the bank that was calling - and now that the card has been frozen and no replacement for 3 weeks you definitley need to put in a letter of complaint. I lost my card a few weeks ago, and within 2 days I had a replacement in my hand. 3 weeks is absurdly a long time to wait. You also need to press for the person who called you and then denied to tell you why they'd frozen the card or what the reason was. That is simply unnacceptable. There will be a trace of it somewhere, unless of course, theres some internal prankster at Abbey who made the call etc.
if the 3 week thing is in the small print somewhere, I'd then consider switching banks! they're all a necessary evil I guess, but if true, then that's a really low level to stoop in customer service !
As for the recent tales here of people getting similar freezes etc, it's not a human initially that 'freezes' the account. There's alot of sophisticated data mining software that uses algorithms to assess your cards usage for fraud purposes. Maybe they've become a little more over zealous recently, but certainly in my experience when use occured abroad