By "non-free" does that mean I have to have a bought version of Mandrake Linux to download and use that?
No, I mean you need to enable the "non-free" software section (software that isn't compatible with the GNU Public License is classified as "non-free" even though it may be free of charge). Since ATI doesn't release the source code for their drivers, it is considered non-free.
To do this, in RPMDrake, you go to the "Media Manager" menu option under the "Options" menu. Then you check the Enabled box next to "Non-free" and "Non-free Updates." Also check the Updates box next to "Non-free Updates."
Also I'm having a helluva time finding a mirror that has the Mandriva 2007.1 Catalyst 7.12 drivers.
In 2007.1 the package seems to be called dkms-ati. I don't have much experience with Mandriva, so I didn't realize they'd renamed it between 2008.0 and 2007.1 when I found the info. It also looks like they're stuck at driver version 8.34.8 which probably doesn't support your card. The problem is 2007.1 is old and not getting functionality updates anymore, just security. 2008.0 has the dkms-fglrx-hd2000 driver package which could support your card.
You've run into the bad combination of trying to use an old version of a distribution with a brand new piece of hardware.