After installing a newer video card into a shuttle PC, it seems to randomly freeze (system becomes completely unresponsive, hard drive light goes out but no error screen) and is unable to reboot without hanging at a black screen unless it is first powered down. Could this be do to a lack of system power?

Its possible. If you have a small power supply and add a peripheral that requires a lot of power it could have that effect. Used to be a 200W PS was sufficient. Now I'm seeing 300W PS as entry level.