Someone recently built a new computer with Windows 8.1 and also had issues with Legions. Just make sure you go through all the Windows updates, and make sure you have the latest version of DirectX. After the updates were installed he was able to get Legions working.