I have found that video cards based on nvidia chips are very successfully used with Linux. I highly advise looking for video cards based on nvidia. Compuvest.com sells many older ( deprecated ) video cards based on nvidia plus new ones. Prices can be below $20.
I found a dual output nvidia video card for $40 at Compuvest. It was way cool that I found a video card that was AGP based since that is what I had on my motherboard. Your mileage may vary. You may have PCI , AGP or various forms of PCIe ( x1, x4 , x16 ).
I have heard that Windows 7 provides much better multiple monitor support .
I like XP so that is what I am using.
One of the more problematic groups of video hardware is the integrated video on your motherboard. Firstly, this hardware may have to be turned on or adjusted via your BIOs settings. This kind of hardware may not support multiple monitors.
In summary... I would stick with nvidia cards for maximum success.
If at first you do not succeed , try restarting your machine multiple times. Check through the BIOS settings. Make sure you click "apply" after changing settings.