Running KaosFroyo v35-1, I kept getting "installation unsuccessful" errors when installing from the market or from this downloaded apk (Thanks a bunch, btw!)
Got it to work this way:
1) Using Root Explorer, renamed gmail.apk to gmail.bak in system\app\
2) Reboot phone
3) Ran the gmail.apk acquired here, though I assume that the market installation may work at this step, too.