I just updated to Windows 8.1 and now CS4 doesn't want to re-install. What do I do?

Maybe it's best to consider a upgrade. At least you can try a trial CC 2014. It might work CS4 but it's quite unlikely as CS4 was developed for Windows XP and Vista. The OS changed and some years have passed since the release of CS4. Adobe Creative Suite - Wikipedia, the free encyclopedia 2008 - 2014. Adobe states: http://helpx.adobe.com/x-productkb/global/windows-8-1-compatability.html

Adobe and Microsoft have worked together to test Creative Cloud and Creative Suite 6 applications for reliability, performance, and user experience when installed on Intel-based systems running Microsoft® Windows® 8.1. There are currently no known issues. Adobe Photoshop® CS5, CS4, and CS3 were also tested with Windows 8.1 and there are currently no known major issues.

As with any new release of an operating system, there could be unexpected issues that arise that were not discovered during testing. If you encounter any issues, report them using the bug reporting form.

Good luck!