"The case has its own 4pin molex which is connected."
I assume you mean the graphics card needs a 4 pin additional molex connector?
Check that the molex connection is fully seated(and try a different connector) and check that the graphics card itself is fully pushed home in its slot.New cards can sometimes need a firm push to locate correctly.
A 450W power supply should be more than enough.....I'm running a Gainward BLISS 7800GS+ card with a generic 460W psu (2x hard drives/2GB RAM?X-Fi sound card and 3.2GHz P4....it's also running Folding@Home so is running at 100% continuously).
However....Have a look at the label on the side panel of the psu and check the +12V amperage rating....some cheaper power supplies can be rather liberal with their overall ratings.You need above 16Amps on that rail (20 or more is preferable)