I'm also with Bank of America (BOA) and they have been good about changing my address, just make sure they get it right! It's a bit fiddly with the credit cards when you collect your reward points, but if you call them directly (use skype) when you have points to cash in, they are good about helping you. They get stumped because of no US address but they've always helped me get it ok.
I recommend you talk to the local branch manager about your move, and ask exactly who can you call if there is an issue? Would it be them or their 800 number? I think it helps to make yourself known to a 'real' person that you could email or call in a pinch for help.
Hope you get it sorted,
Mary