Do you have Google Apps on one of your domains, left over from the days when they gave it away for free to organisations of fewer than 10 users? I do.
Ever tried to tick this box and got an "We are unable to process your request at this time. Please try again later. (Error #1000)"?
A search suggests that many people on "legacy" (free) Google Apps have run into this, but naturally Google aren't going to help unless you become a paying customer.
Fortunately, I stumbled across the solution: after ticking the box and before clicking Save, change one of the other settings on the page as well. I used the catch-all e-mail setting (and then changed it back later). Google are correct that the setting change above takes a few hours to propagate to all your GMail users, but it has now started working for me.