In this particular case, I wouldn't think of asking them to move over. I am pretty strict about mannerisms over food. No phones, no TV, no moving people about once they've started. No way I'm gonna interrupt their evening.

But then again, suppose you flipped the question around, and I was part of couple "A". I'd move over straight away if I saw the restaurant was full and people waiting could sit in the space I'm unnessesarily (sp?) taking up.

I'd say the restaurant is a special case. In the Cinema or on the Underground, I'll ask people to move up if I want them to without much bother.