I also have Crimson Skies and a Radeon 64. It runs slowly enough to be unplayable. I put it on a system with a Hercules Prophet II 64 DVI. It runs great.
This is the first game I've had a problem with. Everything else seems to run great. I called Microsoft and ATI. Neither had a solution. The system is running Windows Me and Direct X 7.0a. All seem to check out.