jn1,
What drivers are you using for your G400? I have VIA KX133 system, reportedly among the worst as far as compatibility with the G400 series of cards, and I've been able to get all my games to run just fine (one required the game patch). I haved used the PD6.01, 6.04, 6.10. I definitely recommend the latest 6.10 drivers, they gave me a little boost in speed and a few minor glitches are now gone. If you have a VIA chipset, you might try uninstalling your Matrox drivers, then uninstall and reinstall the latest VIA 4-in-1 drivers (4.24 is what I use), then install the latest Matrox drivers.
As to the G400 vs the G450, most things I have read point to the G400 as still being a hair faster in 3D gaming. The G450 adds something that the G400 doesn't have in terms of dual head, but what that is escapes me at the moment. Either way, they are both similarly priced, so logic would point to getting the G450 I guess..
You can also overclock the G400 pretty easily with a little program called MGA Tweak, it's at http://www.matroxusers.com. Have been successful with a 25% overclock on my G400 32M DH, which puts the core and memory speeds (though not the RAMDAC) near G400 MAX levels. I'd recommend adding a fan if you do this long term though, people have reported an old PII CPU fan works well.
Good luck!
Aaron