AFAIK, you should be able to change the address on your credit card without providing proof of residence. Card Services are a separate operation from the branch, so she should call them directly.
I don't think the bank can tell her that 'they have to correspond with her'-I have seen plenty of cases where correspondence holds have been placed on accounts. If mail is being sent out without your consent to an incorrect address, this could be an issue for the Data Protection Commissioner, and if the bank does not comply with the request for a corresspondence hold, there should be a formal complaint made to the Financial Regulator.
Other than that, as has been suggested, get some form of proof of residence that the bank are willing to accept. Ask to speak to the manager and explain the situation to them-those on the counter are only following written procedures.