I made an account just to post this.
So I know this topic is old, but I wanted to post a fix here for those of you still having trouble and not wanting to install a third party application. I am posting now because of CitiesXL being available as part of the Humble Bundle so I imagine more people will be playing it.
I am running 3 displayes in Portrait NVSurround. What I figured out from this thread and others is that the key is really that the 800x600 resolution be available. So what I did is this:
I went to the NVIDIA Control Panel to add a custom resolution. What I found when I got there is that since I am running in NVSurround, the custom resolution button did not let me add anything. So I temporarily disabled NVSurround, went back in, added the custom resolution of 800x600, then re-enabled my NVSurround.
Now I can start this game without any trouble.
I imagine this fix will work for ATI / AMD cards with Eyefinity as well. Just be sure in some way to add the custom resolution of 800x600 and all will be good.
EDIT:
After switching back to portrait surround I no longer actually SEE the custom resolution that I added, but apparently that doesnt matter because CitiesXL still works.