Soa como um limite no driver de software livre que você está usando para a sua placa de vídeo. Eu tinha tentado o mesmo no trabalho e recebi o mesmo erro (embora com um tamanho diferente de resolução máxima listado). Instalando os drivers proprietários (ATI) consegui colocar as telas lado a lado.
Em casa, eu tenho a nVidia e já tinha os drivers proprietários instalados quando adicionei uma segunda tela. Aqui está uma captura de tela das configurações de exibição através do gerenciador de configurações da nVidia.