Eu tenho o mesmo problema em um iMac de 27 polegadas rodando o Ubuntu 12.04 64bits.
Tem uma Mobility Radeon HD 4850 da ATI.
Eu recebo a mesma mensagem de erro exata se eu tentar definir os dois monitores para a resolução máxima e, em seguida, organizá-los lado a lado.
Um par de soluções retardadas é mover o segundo monitor abaixo do primeiro, já que aparentemente a resolução completa dos dois combinados neste arranjo é aceita.
Por meio de alguns testes, descobri que a largura máxima da Área de Trabalho parece ser 4000, e adivinho que a altura máxima também é 4000. Também não é um cálculo de área total, já que posso organizar os monitores de tal forma. maneira de usar mais área de tela total do que o arranjo normal seria, e isso é permitido.
Parece ser algo que limita a 4000.
Outra coisa que funcionou para mim é girar meu segundo monitor para que fique na vertical, o que reduziu a largura o suficiente para tornar a resolução aceitável. Isso não funciona muito bem para mim, já que meu segundo monitor parece muito ruim na vertical devido ao design do ângulo de visão do monitor.
Descobri que você pode forçar a resolução através do xorg.conf, mas isso não funciona. A seção da área da tela além de 4000 fica corrompida.