I have the same issue on a 27 inch iMac running Ubuntu 12.04 64bit.
It has an ATI Mobility Radeon HD 4850 in it.
I get the same exact error message if I attempt to set the two monitors to their max resolution, and then arrange them side by side.
A couple of retarded workarounds are to move the second monitor below the first, as apparently the complete desktop resolution of the two combined at this arrangement is accepted.
Through some testing I found that the max Desktop Area width seems to be 4000, and I am going to guess the max height is also 4000. It is not a total area calculation either, as I can arrange the monitors in such a way as to use more total screen area than the normal arrangement would, and that is allowed.
Seems to be something that limits it to 4000.
Another things that worked for me, is to rotate my second monitor so that it is vertical, this reduced the width enough to make the resolution acceptable. This doesn't work very well for me, as my second monitor looks very bad vertical due to the viewing angle design of the monitor.
I found that you can forcibly set the resolution via the xorg.conf however, this doesn't work. The section of the screen area beyond 4000 becomes corrupted.