Gary Nakayama , Jul 10, 2006; 11:35 p.m.
That would be part of scouting. Tell the couple in advance of issues you find like that. "I'll be shooting your formals outside because there is really bad lighting at the alter that will make your formal portraits come out looking bad." And if you have examples to show them, it should impress them that you are doing your homework to give them good photos.
If you can't do advanced scouting before the day of the wedding, at least scout the site early and be prepared to do just as you said, move to a location with better lighting and a pleasing background. I might tell them why you are shooting in a location other than the alter where they might be assuming you would shoot.
Of course if they still want it there just make sure they understand that you can't control the sun and their photos will be like your example.