I have the same issue on my rig. that pc has an I7 2600K stock and a sapphire Radeon HD 6950 2 GB GPU. Now I am running Catalyst 13.1. In one of the previous versions of the driver (up to 12.8 I believe) the game started and worked fine. But now the game doesn't launch anymore. The same counts for Max Payne 2.
I can play the games on my notebook which has an IGPU of the Mobility HD 4200 series with catalyst 12.2 (I rolled back the drivers already because 12.4 and later versions caused glitches in every game)
I don't want to keep the current drivers for all eternity on my main rig, since i own up-to-date games which benefit from the latest drivers.
Quick fixes like compability mode or affinity changes didn't work.
And before you say anything, the release notes didn't mention anything about the max payne games being unsupported.
I hope AMD fixes this in a next driver update, because there are a lot of forums where people with different driver versions suffer from this.