I'm using ATI cards on Linux nearly since the dawn of time (or at least the dawn of Linux ^^). These days, it's a great hardware, as you get updates every month (it's an official AMD/ATI release schedule) and they are on the verge of implementing the last few missing functions people are missing, like AIGLX and the like. Plus, they have begun helping open source authors writing open source drivers for the very latest hardware, so ATI hardware is actually better supported than NVidia (at last... for years, it was opposite).
Since AMD publishes updated drivers frequently, try to use the very latest ones. If you can, use a pre-made installer for your distribution, then it will be painless. Don't use manual installation unless you have no choice: Accidentally mixing components of various drivers will produce problems and/or crashes. Your description sounds like such a case.
I own both, low- and high-end ATI cards (9600 and X1950), and both work flawlessly unless I accidentally mix files from different drivers/versions/packages.
Hint: the command "ldd /path/to/executable" will show you what shared libraries are used. Make absolutely sure that exactly the right "libGL.so" is used. Only the one that was shipped with your currently loaded fglrx kernel module will work correctly.
But as I said, most distributions offer a painless way to do that, by using the regular package manager. Absolutely use that if possible. Google if you don't know if/how it works on your distro.
And if your card is a Radeon 9200 or below, follow dougdahls advice, use the open source driver and not the closed source one. Again, try to use the distribution's package manager to install it.